题解 | #An Easy Problem#

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<utility>
const int MAXN=2e5+10;
int h[MAXN],rh[MAXN],ne[MAXN],e[MAXN],w[MAXN];
int st[MAXN];
int dist[MAXN],cnt[MAXN];
int idx=0;
int n,m,s,t,k;
typedef std::pair<int,int>PII;
typedef std::pair<int,PII>PIII; 
using namespace std;

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

void dijistra()
{
    priority_queue <PII,vector<PII>,greater<PII>> heap;
    heap.push({0,t});
    dist[t]=0;
    while(!heap.empty())
    {
        PII top=heap.top();
        heap.pop();
        int distance=top.first,ver=top.second;
        if(st[ver]) continue;
        st[ver]=1;
        for(int i=rh[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>distance+w[i])
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}

int astar()
{
    priority_queue <PIII,vector<PIII>,greater<PIII>> heap;
    heap.push({dist[s],{0,s}});
    while(!heap.empty())
    {
        PIII top=heap.top();
        heap.pop();
        int distance=top.second.first,ver=top.second.second;
        cnt[ver]++;
        if(cnt[t]==k) return distance;
        
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(cnt[j]<k)
            heap.push({distance+w[i]+dist[j],{distance+w[i],j}});
        }
    }
    return -1;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(rh,-1,sizeof rh);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(h,a,b,c);
        add(rh,a,b,c);
    }
    cin>>s>>t>>k;
    memset(dist,0x3f,sizeof dist);
    dijistra();
    if(s==t) k++; 
    cout<<astar();
}