题解 | #Rinne Loves Graph#

思路

求能从 1 号点到达 n 号点 并且 满足相关条件的最短路
条件：穿过的被***城镇 不能超过 K 个

解法：最短路 ＋ dp

dist[i][j]：从起点开始 穿过了j个被***的城市 到达i点的 最短距离
ps：dist 最后一定是最短距离，但中间过程的值不一定是，因为后续可能被再次更新

所以我们只需要求 min( dist[n][0] , dist[n][1] , dist[n][2] , ...... , dist[n][k] )

至于 dist ，我们在 dijkstra 中求得
为了求得 dist 我们需额外 将 当前穿过被***城市的数量 加入到队列中去，这点与 以往的 dijkstra 不同，平常 只是将 距离（distance） 和 点的序号（id）加入，本题我们额外加入了 cnt
它们三者之间的关系是 dist[id][cnt] = distance，单调队列（小根堆）会按照 distance 从小到大实时排序

入队的时候 分两种情况 ：
① a[id] = 1，id 这个点是***城市，所以其到达 j 点时 cnt 要加 1 ,据此来对 dist[j][cnt+1] 进行更新

② a[id] = 0，id 这个点是非***城市，所以其到达 j 点时 cnt 不变 ,据此来对 dist[j][cnt] 进行更新

什么时候 执行入队操作 ？ 当前点 即代码中的 j 点 的状态被更新了的时候 . j 点状态 若不被更新 那么j点能到达的点 也不会被更新，所以 j 点没有入队的必要

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 810,M = 8010;

struct node{
   int distance,id,cnt;
   bool operator < (const node & b) const{
       return distance > b.distance;
   }
}point;
bool st[N][20];   // st[i][j]=true 表示 从起点开始穿过了j个被***的城市 才到到i点的最短路 被确定
int dist[N][20];   // dist[i][j] :从起点开始 穿过了j个被***的城市 到达i点的 待定（暂时的）最短距离
int a[N],h[N],e[M],w[M],ne[M],idx;
int n,m,k;

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1][0]=0;

    priority_queue<node>heap;  // 小根堆，因为重载了小于号
    heap.push({0,1,0});   

    while(heap.size()){
        auto t=heap.top();
        heap.pop();
        int id=t.id,distance=t.distance,cnt=t.cnt;

        if(cnt>k||st[id][cnt]) continue;

        st[id][cnt]=true;
        for(int i=h[id];i!=-1;i=ne[i]){
            int j=e[i];
            if(a[id]==1) {
                if(dist[j][cnt+1]>distance+w[i]){
                    dist[j][cnt+1]=distance+w[i];
                    heap.push({dist[j][cnt+1],j,cnt+1});
                }      
            }
            else {
                if(dist[j][cnt]>distance+w[i]){
                    dist[j][cnt]=distance+w[i];
                    heap.push({dist[j][cnt],j,cnt});
                }
            }
        }
    }

     int res=0x3f3f3f3f;
     for(int i=0;i<=k;i++) res=min(res,dist[n][i]);
     return res==0x3f3f3f3f?-1:res;
}

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(h,-1,sizeof h);

    while(m--){
        int a,b,w;
        cin>>a>>b>>w;
        add(a,b,w),add(b,a,w);
    }

    cout<<dijkstra()<<endl;

    return 0;
}