求第k短路的长度，如果没有，输出-1。
/* k短路模板 注意当s=t时，k++。 */ #include<iostream> #include<cstdio> #include<queue> #define N 1010 #define M 100010 using namespace std; int head1[N],head2[N],dis[N],vis[N],n,m,k,cnt; bool flag; struct node { int v,pre,t; };node e1[M],e2[M]; struct Node { int from,g,f; bool operator< (Node x) const { if(x.f!=f)return x.f<f; return x.g<g; } }; void add(int i,int x,int y,int z) { e1[i].v=y; e1[i].t=z; e1[i].pre=head1[x]; head1[x]=i; e2[i].v=x; e2[i].t=z; e2[i].pre=head2[y]; head2[y]=i; } void spfa(int s,int t) { queue<int> q; for(int i=1;i<=n;i++)dis[i]=N*M; vis[s]=1;dis[s]=0; q.push(s); while(!q.empty()) { int x=q.front();q.pop(); vis[x]=0; for(int i=head2[x];i;i=e2[i].pre) if(dis[e2[i].v]>dis[x]+e2[i].t) { dis[e2[i].v]=dis[x]+e2[i].t; if(!vis[e2[i].v]) { vis[e2[i].v]=1; q.push(e2[i].v); } } } } void a_star(int s,int t) { if(s==t)k++; priority_queue<Node> q; Node u;u.from=s;u.g=0;u.f=dis[s]; q.push(u); while(!q.empty()) { u=q.top();q.pop(); if(u.from==t) { cnt++; if(cnt==k) { printf("%d",u.f); flag=true; return; } } for(int i=head1[u.from];i;i=e1[i].pre) { Node v; v.from=e1[i].v; v.g=u.g+e1[i].t; v.f=v.g+dis[e1[i].v]; q.push(v); } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(i,x,y,z); } int s,t; scanf("%d%d%d",&s,&t,&k); spfa(t,s); a_star(s,t); if(!flag)printf("-1"); return 0; }