题目描述

给定一张N个点（编号1,2…N），M条边的有向图，求从起点S到终点T的第K短路的长度，路径允许重复经过点或边。

输入格式
第一行包含两个整数N和M。

接下来M行，每行包含三个整数A,B和L，表示点A与点B之间存在有向边，且边长为L。

最后一行包含三个整数S,T和K，分别表示起点S，终点T和第K短路。

输出格式
输出占一行，包含一个整数，表示第K短路的长度，如果第K短路不存在，则输出“-1”。

数据范围
1≤S,T≤N≤1000,
0≤M≤105,
1≤K≤1000,
1≤L≤100

样例

输入样例：
2 2
1 2 5
2 1 4
1 2 2
输出样例：
14

先逆向求出终点到每个点的最短路 作为估计函数
在bfs中 按照到当前点的距离加估价函数排序
在第k次出现终点时即为答案
注意自己连自己时 要排除0的情况
无答案时要输出-1

C++ 代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<set>
#define PII pair<int,int>
using namespace std;
int read(){
    int x=0,y=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*y;
}
const int maxn=1e3+7;
const int maxm=1e5+7;
struct rec{int x,val;};//当前点和当前的代价 
bool operator <(const rec &a,const rec &b){return a.val>b.val;}//小根堆 
int n,m,en,en1,s,t,k;//n点 m边  en,en1前向星中的辅助变量 s起点 t终点 第k条边 
int dis[maxn],dis1[maxn],head[maxn],head1[maxn];//dis 正向距离 dis1 逆向存图距离 head/head1 辅助变量 
bool vis[maxn],vis1[maxn];//当前点是否访问过 
struct edge{int nxt,v,w;}eg[maxm<<1],eg1[maxm];
void insert(int u,int v,int w)
{
    eg[++en].nxt=head[u];
    eg[en].v=v;
    eg[en].w=w;
    head[u]=en; 
}
void insert1(int u,int v,int w)
{
    eg1[++en1].nxt=head1[u];
    eg1[en1].v=v;
    eg1[en1].w=w;
    head1[u]=en1;
}
void dijkstra(int ss)//逆向最短路 
{
    set<PII,less<PII> >s;
    memset(dis1,0x3f,sizeof(dis1)); dis1[ss]=0;
    memset(vis1,0,sizeof(vis1));vis1[ss]=0;
    s.insert(make_pair(0,ss));
    while(!s.empty())
    {
        set<PII,less<PII> >::iterator it=s.begin();
        int u=it->second;
        s.erase(*it);
        vis1[u]=1;
        for(int i=head1[u];i;i=eg1[i].nxt)
        {
            int v=eg1[i].v,w=eg1[i].w;
            if(dis1[v]>dis1[u]+w&&!vis1[v])
            {
                s.erase(make_pair(dis1[v],v));
                dis1[v]=dis1[u]+w;
                s.insert(make_pair(dis1[v],v)); 
            }
        }
    }
}
int f(int x){ return dis1[x];}  //估计函数 
priority_queue<rec>q;//小根堆 按照距离加估价函数排序 
int ans;
bool bfs()
{
    int tep=0;
    rec r;
    if(s==t)tep--;//自身到自身... 排除0的情况 
    dis[s]=0;
    r.x=s;r.val=f(s);
    q.push(r);
    while(!q.empty()){
        r=q.top();
        q.pop();
        int x=r.x,val=r.val;
        if(x==t)tep++;
        if(tep==k) {ans=val-f(x);return 1;}
        for(int i=head[x];i;i=eg[i].nxt){
            int v=eg[i].v,w=eg[i].w;
            dis[v]=dis[x]+w;
            r.x=v,r.val=val-f(x)+w+f(v);
            q.push(r);
        } 
    }
    return 0;
}

int main(){
    n=read(),m=read();
    int u,v,w;
    for(int i=1;i<=m;i++){
    u=read(),v=read(),w=read();
    insert(u,v,w);
    insert1(v,u,w);
    }
    memset(dis,0x3f,sizeof(dis));
    s=read(),t=read(),k=read();
    if(m==0) {puts("-1");return 0;}
    dijkstra(t);
    if(bfs())cout<<ans<<endl;
    else puts("-1");
    return 0;
}
/*
3 5
2 3 72
2 3 12
1 2 12
3 1 48
2 2 24
3 3 1
//132
*/