题目大意：
给出一个图，然后给出一个起点个一个终点，求这两点间的第K短路。
本题中是可以走重复的路的，所以如果一张图中有一个环的话，无论求第几短路都是存在的。
/* 边可以重复走， 不严格的k短路 A* 估价函数为dis（起点，i）+dis（i，终点） 1、反向图上求出终点到每个点的最短路 2、起点入优先队列， 队首出队， 如果队首是终点，而且是第k次出队， 那么当前距离就是k短路 如果队首不是终点，便利与当前点连接的所有的点，入队 细节1：优先队列出入队不用vis数组判重，因为边可以重复走 细节2：如果第1步中，起点与终点不连通，输出-1结束， 否则进入A*，没有vis数组，出现环会死循环 细节3：如果起点=终点，令k++，因为起点会立即出队 */ #include<iostream> #include<cstdio> #include<queue> #define inf 999999999 using namespace std; int n,m,s,t,k,num1,head1[1010],num2,head2[1010],dis[1010]; bool vis[1010]; struct node{ int to,pre,v; }e1[100010],e2[100010]; void Insert1(int from,int to,int v){ e1[++num1].to=to; e1[num1].v=v; e1[num1].pre=head1[from]; head1[from]=num1; } void Insert2(int to,int from,int v){ e2[++num2].to=to; e2[num2].v=v; e2[num2].pre=head2[from]; head2[from]=num2; } void spfa(){ for(int i=1;i<=n;i++)dis[i]=inf; queue<int>q; q.push(t);dis[t]=0;vis[t]=1; while(!q.empty()){ int now=q.front();q.pop();vis[now]=0; for(int i=head2[now];i;i=e2[i].pre){ int to=e2[i].to; if(dis[to]>dis[now]+e2[i].v){ dis[to]=dis[now]+e2[i].v; if(!vis[to]){ q.push(to); vis[to]=1; } } } } } struct Node{ int d,id; bool operator < (Node x)const{ return d+dis[id]>x.d+dis[x.id]; } }nxt; void Astar(){ if(dis[s]==inf){ printf("-1"); return; } if(s==t)k++; priority_queue<Node>q; int cnt=0; Node now; now.id=s; now.d=0; q.push(now); while(!q.empty()){ now=q.top();q.pop(); if(now.id==t){ cnt++; if(cnt==k){ printf("%d",now.d); return; } } for(int i=head1[now.id];i;i=e1[i].pre){ int to=e1[i].to; nxt.id=to; nxt.d=now.d+e1[i].v; q.push(nxt); } } printf("-1"); } int main(){ scanf("%d%d",&n,&m); int x,y,z; for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); Insert1(x,y,z); Insert2(x,y,z); } scanf("%d%d%d",&s,&t,&k); spfa(); Astar(); return 0; }