k短路模板（以POJ 2449 为例）

题目：点击打开链接

题意：给出一个图，然后给出一个起点个一个终点，求这两点间的第K短路。本题中是可以走重复的路的，所以如果一张图中有一个环的话，无论求第几短路都是存在的。路径长度一样，经过的边集不同属于两种不同的情况。

分析：k短路模板题，A*+dijkstra，注意当s == t的时候，需要计算第k+1短路。因为s到t这条距离为0的路不能算是这k短路里边。A*入门参考https://www.cnblogs.com/zhoug2020/p/3468167.html，A*的本质是启发式搜索，理论复杂度为O(nk)，k短路入门参考https://blog.csdn.net/drin_e/article/details/72569024。

代码：

#pragma comment(linker, "/STACK:102400000,102400000")
///#include<unordered_map>
///#include<unordered_set>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iomanip>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cctype>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<map>
using namespace std;
#define pt(a) cout<<a<<endl
#define debug test
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f
#define eps 1e-10
#define PI acos(-1.0)
const ll mod = 1e9+7;
const int N = 1e6+10;

ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int n,m,s,t,k,d[N],ct[N];
struct eg{
    int to,w;
};
vector<eg> g1[N],g2[N];

struct nd{
    int u,g,h;
    bool operator < (const nd & a) const {
        return g+h>a.g+a.h;
    }
};

void init() {
    for(int i=1;i<=n;i++) g1[i].clear(),g2[i].clear();
    mst(ct,0);
}

void dij(int s) {
    mst(d,inf);
    d[s]=0;
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    pq.push({0,s});
    while(!pq.empty()) {
        pii tp=pq.top(); pq.pop();
        int u=tp.se;
        if(d[u]!=tp.fi) continue;
        for(int i=0;i<g2[u].size();i++) {
            eg v=g2[u][i];
            if(d[u]+v.w<d[v.to]) {
                d[v.to]=d[u]+v.w;
                pq.push({d[v.to],v.to});
            }
        }
    }
}

int astar(int s) {
    if(d[s]==inf) return -1;
    priority_queue<nd> pq;
    pq.push({s,0,d[s]});
    while(!pq.empty()) {
        nd tp=pq.top(); pq.pop();
        int u=tp.u;
        ct[u]++;
        if(ct[t]>=k) return tp.g;
        if(ct[u]>k) continue;///剪枝
        for(int i=0;i<g1[u].size();i++) {
            pq.push({g1[u][i].to,tp.g+g1[u][i].w,d[g1[u][i].to]});
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    while(~scanf("%d%d",&n,&m)) {
        init();
        for(int i=1;i<=m;i++) {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            g1[a].pb({b,c});
            g2[b].pb({a,c});
        }
        scanf("%d%d%d",&s,&t,&k);
        if(s==t) k++;///注意特判
        dij(t);
        printf("%d\n",astar(s));
    }
    return 0;
}