题目描述

给定一张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* 时间复杂度 O( mlogn + ?)

在做这题之前要明白这题最重要的性质：小根堆每次出堆且是终点第几次出堆就是第几短路。
然后设计代价函数，从该点到终点的最短距离，我们可以逆向求一遍Dijkstra的得到
最后注意细节，当S==T时时没有路径的，但题目要求必须要有路径，所以距离为0的这条路不能作为最短路，所以K要++
剩下就没有什么难度了，难的还是优先队列BFS的性质，详情请看代码。。。~.~

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

#define pii pair<int,int>
#define piii pair<int,pii>

using namespace std;

const int N = 1010;

int n,m;

int S,T,K;

vector<int> ver[N],edge[N],rver[N],redge[N];

bool st[N];

int dist[N];

void dijkstra()
{
    memset(dist,0x3f,sizeof dist);

    dist[T] = 0;

    priority_queue<pii,vector<pii>,greater<pii> > heap;

    heap.push({0,T});

    while(heap.size())
    {
        int t = heap.top().second;
        heap.pop();
        if(st[t]) continue;
        st[t] = true;
        for(int i=0;i<rver[t].size();i++)
        {
            int p = rver[t][i],d = redge[t][i];
            if(dist[p] > dist[t] + d)
            {
                dist[p] = dist[t] + d;
                heap.push({dist[p],p});
            }
        }
    }
}

int astar(){

    priority_queue<piii,vector<piii>,greater<piii> > heap;

    int cnt = 0;

    heap.push({dist[S],{0,S}});

    while(heap.size())
    {
        piii temp = heap.top();
        heap.pop();
        int t1 = temp.second.first;
        int t2 = temp.second.second;
        if(t2 == T) cnt ++;
        if(cnt == K) return t1;
        for(int i = 0;i < ver[t2].size();i++)
        {
            int p = ver[t2][i], d = edge[t2][i];
            heap.push({t1 + d + dist[p],{d + t1,p}});

        } 
    }
    return -1;
}

int main(){

    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);

    scanf("%d%d",&n,&m);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        ver[a].push_back(b);
        edge[a].push_back(c);
        rver[b].push_back(a);
        redge[b].push_back(c);
    }

    scanf("%d%d%d",&S,&T,&K);
    if(S==T) K++;

    dijkstra();

    printf("%d\n",astar());



    return 0;
}