Nowcoder contest 370B Rinne Loves Graph 【分层图最短路】

<题目链接>

题目大意：

Island 是有一些奇怪的城镇和道路构成的（题目需要，游戏党勿喷），有些城镇之间用双向道路连接起来了，且每条道路有它自己的距离。但是有一些城镇已经被派兵戒严，虽然主角可以逆天改命强闯，但是为了体验该游戏的平衡性，他们只能穿过不超过 K 次被戒严的城镇。

定义“穿过”：从一个戒严的点出发到达任意一个点，都会使得次数加1

现在他们想从 1 号城镇最快的走到 n 号城镇（即出口），现在他们想让你告诉他们最短需要走多少路。
$\mathrm{2\le n\le 800,1\le m\le 4000,1\le k\le 10,1\le w\le 10^6}$

解题分析：

本题很明显是一道分成图最短路的题。主要的就是怎么处理"穿过"K个点，我是通过在最短路松弛过程中，判断下一个点是否是封锁点，是的话，就要利用分层图的性质进行松弛。因为题目规定的是穿过k个封锁点，所以我们需要对起点和终点进行处理。如果起点是封锁点，那么k--,如果终点是封锁点k++，因为起点是一定要穿过的，而终点穿不过。

#include <bits/stdc++.h>
using namespace std;

#define clr(a,b) memset(a,b,sizeof(a))
#define rep(i,s,t) for(int i=s;i<=t;i++)
typedef long long ll;
const int N = 805, M = 4005;
int n,m,k,cnt;
int isgo[N],head[N];

template<typename T>
inline void read(T&x){
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar(); }
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
struct Edge{
    int to,nxt;ll w;
}edge[M<<1];

struct Node{
    int loc,lev;ll dist;
    Node(int _loc=0,int _lev=0,ll _dist=0):loc(_loc),lev(_lev),dist(_dist){}
    bool operator < (const Node &tmp)const{ return dist>tmp.dist; }
}node[N][15];
int vis[N][15];

inline void init(){ cnt=0;clr(head,-1); }
inline void add(int u,int v,ll w){
    edge[++cnt].to=v,edge[cnt].nxt=head[u];
    edge[cnt].w=w;head[u]=cnt;
}
void Dij(){
    rep(i,1,n) rep(j,0,k){
        node[i][j].loc=i,node[i][j].lev=j;
        node[i][j].dist=1e18;vis[i][j]=0;
    }
    priority_queue<Node>q;
    node[1][0].dist=0;
    q.push(node[1][0]);
    while(!q.empty()){
        Node now=q.top();q.pop();
        int loc=now.loc,lev=now.lev;
        if(vis[loc][lev])continue;
        vis[loc][lev]=1;
        for(int i=head[loc];~i;i=edge[i].nxt){
            int v=edge[i].to;ll cost=edge[i].w;
            if(!isgo[v] && node[v][lev].dist>node[loc][lev].dist+cost){     //进行同层次建进行正常的松弛
                node[v][lev].dist=node[loc][lev].dist+cost;
                q.push(Node(v,lev,node[v][lev].dist));
            }
            if(isgo[v] && (lev+1)<=k && node[v][lev+1].dist>node[loc][lev].dist+cost){  //不是封锁点的就没有必要利用分层图进行松弛，因为在正常的一层就已经松弛了
                node[v][lev+1].dist=node[loc][lev].dist+cost;
                q.push(Node(v,lev+1,node[v][lev].dist));
            }
        }
    }
}
int main(){
    init();
    read(n);read(m);read(k);
    rep(i,1,n) read(isgo[i]);
    rep(i,1,m){
        int u,v;ll w;read(u);read(v);read(w);
        add(u,v,w);add(v,u,w);
    }
    if(isgo[1])k--;
    if(isgo[n])k++;
    Dij();
    ll ans=1e18;rep(i,0,k)ans=min(ans,node[n][i].dist);
    printf("%lld
",ans);
}