算法 A*算法

有些数据比较讨厌，当起点和终点重合的时候最短路肯定他本身，但由于条件中已经给出，最少要包括一条边，那么当起点与终点重合的时候那么就需要把k++就行啦~~
求第K短路 朴素的做法就算是先建立一个小根堆在依次枚举每个队头的点把它加进去，但是时间复杂度太高，用astart合适。
这种做法要把所有边加进来，而其他情况都是需要判断这个点的距离是否更小。

一种优化 每次出队一个点的时候记录这个点出队几次， 再更新的时候判断当前点是否出队>= K次如果是就不入队，反子入队，因为假如这个点已入队k次代表他更新的点也入队k次，当它下次入队，那么他跟更新的点就会第k+1次更新，显然不对，这是判断无解的情况的优化，如果存在第k条短路，那么这个判断等同于无效。还不明白的话，看看测试点最后一个就明白了。

C++ 代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <cstring>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int N = 1010, M = 2e5 + 10;

int h[N], rh[N], e[M], ne[M], w[M], idx;
bool st[N];
int dist[N];
int n, m, s, T, k;

void add(int h[], int a, int b, int c)
{
    e[++ idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    w[idx] = c;
}

void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII> > heap;
    heap.push({0, T});
    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int av = t.y, distance = t.x;
        if(st[av])continue;
        st[av] = true;
        for(int i = rh[av]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int Astart()
{
    dijkstra();
    priority_queue<PIII, vector<PIII>, greater<PIII> > heap;
    heap.push({dist[s], {0, s}});
    int cnt = 0;
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int av = t.y.y, d = t.y.x;
        if(av == T)cnt ++;
        if(cnt == k)return d;

        for(int i = h[av]; ~i; i = ne[i])
        {
            int j = e[i];
            heap.push({dist[j] + d + w[i], {d + w[i], j}});
        }
    }
    return  -1;
}

int main()
{
    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    cin >> n >> m;
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(h, a, b, c);
        add(rh, b, a, c);
    }
    cin >> s >> T >> k;
    if(s == T)k ++;
    cout << Astart() << endl;
    return 0;
}