第K最短路问题
第一行包含两个整数N和M（1 <= N <= 1000,0 <= M <= 100000）。 站的编号从1到N.接下来M行中的每一行包含三个整数A，B和T（1 <= A，B <= N，1 <= T <= 100）。 代表顶点A到B的边权值为T。
最后一行由三个整数S，T和K组成（1 <= S，T <= N，1 <= K <= 1000）。
第K个最短路径的值， 如果不存在第K个最短路径，则应输出-1。
2 2 1 2 5 2 1 4 1 2 2
14
#include<bits/stdc++.h>using namespace std;
int n,m,ans[1011],S,T,K;int tu[1011];
bool shuchu=0;
vector<int>b[1011],zhi[1011],c[1011],zhic[1011];
bool cha[1001];queue<int>q;
void pan()
{ for(int i=1;i<=n;i++)
{
tu[i]=100000000;
}
tu[T]=0;
q.push(T);
while(q.empty()==0)
{
int u=q.front();q.pop(),cha[u]=0;
for(int i=0;i<c[u].size();i++)
{
if(tu[c[u][i]]>tu[u]+zhic[u][i])
{
tu[c[u][i]]=tu[u]+zhic[u][i];
if(!cha[c[u][i]])
{
cha[u]=1;q.push(c[u][i]);
}
}
}
}
return;
}struct node
{ int d,zhi;
}k,ji;priority_queue<node> a;bool operator <(const node &a,const node &b){
return a.zhi+tu[a.d]>b.zhi+tu[b.d];
}void bfs()
{ if(S==T)
K++;
a.push((node){S,0});
while(a.empty()==0)
{
k=a.top();a.pop();
ans[k.d]++;
if(ans[T]==K)
{
cout<<k.zhi;
shuchu=1;
return;
}
if(ans[k.d]>K)
continue;
for(int i=0;i<b[k.d].size();i++)
a.push((node){b[k.d][i],k.zhi+zhi[k.d][i]});
}
}int main()
{ scanf("%d%d",&n,&m);
int x,y,z;
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
b[x].push_back(y);
zhi[x].push_back(z);
c[y].push_back(x);
zhic[y].push_back(z);
}
scanf("%d%d%d",&S,&T,&K);
pan();
bfs();
if(shuchu==0)
{
printf("%d",-1);
}
return 0;
}用tu【】记录当前点到终点最短距离，bfs函数搜索中，每个点被搜索的次数都小于K（spfa打错了，调试了好几天）