题目描述

给定一张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

A*本人第一道题也是练手的板子题

估价函数为各个点到终点的最短路所以逆向SPFA跑一波即可。然后优先队列入队出队各个节点，优先队列的排序规则为当前总共的路径长度加上估值的和的最小值,然后k次出队代表了k短路直接求解即可

注意有可能不是一个连通的图，所以要判断一下起点与终点是否连通，其次还有可能边个数为0，所以最后如果跑不出来k短路那么输出-1,还有自己到自己的k短路,这种情况不算第一种0的

C++ 代码

#include <bits/stdc++.h>
using namespace std;
long long dis[1005],bk[1005];//dis代表SPFA的单源最短路的记录,bk是SPFA过程中的辅助数组
struct edge//edge代表边的结构体
{
    int e,v;
};
struct node//A*内每个节点的node结构体
{
    long long st,l,f;
    bool operator<(const node&a) const//重载小于号规定优先队列的排序为l+f(p)(也就是当前的总长度与估价函数值的和)
    {
        return a.l+a.f<l+f;
    }
};
vector<edge> G[1005],GG[1005];//定义两个存图的vector,G是正向的,GG是逆向的.因为是有向图所以逆向SPFA需要用逆向存图的GG
const int inf=INT_MAX;//SPFA用的inf
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int s,e,v;
        scanf("%d%d%d",&s,&e,&v);
        G[s].push_back((edge){e,v});//模拟邻接表存图
        GG[e].push_back((edge){s,v});
    }
    int st,ed,tm;
    scanf("%d%d%d",&st,&ed,&tm);
    for(int i=1;i<=n;i++)//初始化dis数组
    dis[i]=i==ed?0:inf;
    queue<int> q;
    q.push(ed);
    while(q.size())//逆向SPFA
    {
        int p=q.front();
        q.pop();
        bk[p]=0;
        for(int i=0;i<GG[p].size();i++)
        {
            if(dis[GG[p][i].e]>dis[p]+GG[p][i].v)
            {
                dis[GG[p][i].e]=dis[p]+GG[p][i].v;
                if(!bk[GG[p][i].e])
                {
                    bk[GG[p][i].e]=1;
                    q.push(GG[p][i].e);
                }
            }
        }
    }
    if(dis[st]==inf)//第一次判断连通性
    return printf("-1"),0;
    priority_queue<node> Q;
    Q.push((node){st,0,0});
    int cntt=0;
    if(ed==st)tm++;//第二个判断是不是自己到自己
    while(Q.size())//A*
    {
        node p=Q.top();
        Q.pop();
        if(p.st==ed)//判断是否为K短路
        {
          cntt++;
          if(cntt==tm)//如果是取出
          return printf("%lld",p.l),0;
        }
        for(int i=0;i<G[p.st].size();i++)//无脑入队各个节点
        Q.push((node){G[p.st][i].e,G[p.st][i].v+p.l,dis[G[p.st][i].e]});
    }
    printf("-1");//如果main不自己返回输出-1
}