题解 | #Rinne Loves Graph#

优先队列一个节点塞三个元素，类似于记忆化 好的我先承认我没学过动态规划，在看到这个题之前，我刚刚完成了dij+heap的模版题，然后我结合两大搜索，写出了这个代码

下面分析过程 1.一个节点是1，那么是要计入次数的，就是num要随着这次搜索+1。 2.在邻接表存储dij算法的遍历时，不需要更新最小的边，因为这个算***遍历所有边，无论大边小边。 所以，可以在每一次push节点时，额外存储一个变量，就是以一个三元组tuple，也可以写结构体， 这样就依旧能以O（mlogn)计算出，

(第一次写最短路,思路可能有缺陷TvT)

//https://ac.nowcoder.com/acm/problem/17511
#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
#define inf 0x3f3f3f3f
#define forn(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef pair<int,int> PII;
typedef tuple<int,int,int> TII;
const int N=1e5+10;
int n,m,k,cnt;
int h[N],e[N],w[N],ne[N],idx;
int dist[N],vis[N],a[N];
void add(int a,int b,int c) {
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dijkstra() {
    for (int i = 1; i <= n; ++i) dist[i]=inf;
    dist[1]=0;
    priority_queue<TII,vector<TII>,greater<TII> > q;

    q.push({0,1,0});
    while (!q.empty()) {
        cnt=0;
        auto [dis,tar,num]=q.top();
        q.pop();
        if (vis[tar])continue;
        if (a[tar])num++;
        vis[tar]=1;
        for (int i=h[tar];i!=-1;i=ne[i]) {
            int j=e[i];
            if (dis+w[i]<dist[j]) {
                if (num>k)continue;
                dist[j]=dis+w[i];
                q.push({dist[j],j,num});

            }
        }
    }
    if (dist[n]==inf)return -1;
    return dist[n];
}
int main() {
    js;cin>>n>>m>>k;
    memset(h,-1,sizeof(h));
    for (int i=1;i<=n;++i)cin>>a[i];
    for (int i=0;i<m;++i) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    int ret=dijkstra();
    cout<<ret<<endl;
    return 0;
}