Analysis

$\ \ \ \ \ \ \ $A* 算法，是带有 “估价函数” 的搜索，维护一个堆（就用优先队列实现啦），不断从堆中取出 “当前代价+未来估价” 最小的状态进行扩展。其中估价函数应遵从 “估价不大于未来实际最小代价” 的原则以保证正确性。
　　这道题目，估价函数其实就是 “每个点到终点的最短路” ，那么显而易见要先建个反图跑个以终点为单源的最短路。
　　然后，就 优先队列 bfs 瞎走，等到终点第 K 次从队列中取出时，即为所求。这道题目有几个小坑需要注意：1、判断无解有两种情况，一是无法到达，二是不存在第 K 短（K 太大了受不了~ ）；2、题目要求至少需要存在一条边，所以若到达终点代价为0（起点和终点为同一个点）时，这次取出终点不能算！！

#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
inline int read()
{
    int x=0;bool f=false;
    char ch=getchar();
    while(ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}
struct edge{int y,d,next;}a[100010],b[100010];int len,last[1010],lst[1010];
inline void ins(int x,int y,int d) {a[++len].y=y;a[len].d=d;a[len].next=last[x];last[x]=len;}
inline void ins2(int x,int y,int d) {b[len].y=y;b[len].d=d;b[len].next=lst[x];lst[x]=len;}
struct node
{
    int dis,x,step;
    friend bool operator <(const node a,const node b)
        {return a.dis>b.dis;}
};
priority_queue<node> q;
int dis[1010]/*到终点的最短路*/;bool v[1010];
void dijkstra(int ed)
{
    while(!q.empty()) q.pop();
    memset(v,false,sizeof(v));
    memset(dis,0x3f,sizeof(dis));
    q.push((node){0,ed,0});dis[ed]=0;
    while(!q.empty())
    {
        int x=q.top().x;q.pop();
        if(v[x]) continue;v[x]=true;
        for(int k=lst[x];k;k=b[k].next)
        {
            int y=b[k].y;
            if(dis[x]+b[k].d<dis[y])
            {
                dis[y]=dis[x]+b[k].d;
                q.push((node){dis[y],y,0});
            }
        }
    }
}
int main()
{
    int n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read(),d=read();
        ins(x,y,d);ins2(y,x,d);
    }
    int st=read(),ed=read(),T=read();
    dijkstra(ed);
    if(dis[st]==0x3f3f3f3f) {puts("-1");return 0;}
    while(!q.empty()) q.pop();
    q.push((node){dis[st],st,0});
    while(!q.empty())
    {
        node now=q.top();q.pop();
        if(now.x==ed && now.step!=0) {if(!--T) {printf("%d\n",now.dis);return 0;}}
        for(int k=last[now.x];k;k=a[k].next)
        {
            int y=a[k].y;
            q.push((node){now.step+a[k].d+dis[y],y,now.step+a[k].d});
        }
    }
    puts("-1");
    return 0;
}