話不多說先上例題。。

acwing：178. 第K短路

給定一張?NN?個(gè)點(diǎn)（編號?1,2…N1,2…N），MM?條邊的有向圖，求從起點(diǎn)?SS?到終點(diǎn)?TT?的第?KK?短路的長度，路徑允許重復(fù)經(jīng)過點(diǎn)或邊。

注意：?每條最短路中至少要包含一條邊。

輸入格式

第一行包含兩個(gè)整數(shù)?NN?和?MM。

接下來?MM?行，每行包含三個(gè)整數(shù)?A,BA,B?和?LL，表示點(diǎn)?AA?與點(diǎn)?BB?之間存在有向邊，且邊長為?LL。

最后一行包含三個(gè)整數(shù)?S,TS,T?和?KK，分別表示起點(diǎn)?SS，終點(diǎn)?TT?和第?KK?短路。

輸出格式

輸出占一行，包含一個(gè)整數(shù)，表示第?KK?短路的長度，如果第?KK?短路不存在，則輸出??1?1。

數(shù)據(jù)范圍

1≤S,T≤N≤10001≤S,T≤N≤1000,
0≤M≤1040≤M≤104,
1≤K≤10001≤K≤1000,
1≤L≤1001≤L≤100

輸入樣例：

2 2
1 2 5
2 1 4
1 2 2

輸出樣例：

14

?思路：

整體思路就是先逆向求一次dijkstral，將各點(diǎn)到目標(biāo)點(diǎn)的最短路求出來，以此作為A*的估計(jì)值。然后在采用A*求第K短路，當(dāng)?shù)贙次目標(biāo)點(diǎn)出隊(duì)列是，返回值即可。注意起點(diǎn)終點(diǎn)一直時(shí)需要將k+1，將原地不動的情況除去。

上代碼：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
#define y second
#define x first
const int N=1010,M=3e4+10;
int s, t ,k;
int n,m;
int h[N],h2[N],e[M],ne[M],w[M],idx;
int dis[N],cnt[N];
bool st[N];
void add(int h[],int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstral(){memset(dis,0x3f,sizeof(dis));priority_queue<PII,vector<PII>,greater<PII>>q;dis[t]=0;q.push({0,t});while(q.size()){auto T=q.top();q.pop();int u=T.y;if(st[u]){continue;}st[u]=true;for(int i=h2[u];~i;i=ne[i]){int j=e[i];if(st[j]){continue;}if(dis[j]>dis[u]+w[i]){dis[j]=dis[u]+w[i];q.push({dis[j],j});}}}
}
int astar(){priority_queue<PIII,vector<PIII>,greater<PIII>> q;q.push({dis[s],{0,s}});while(q.size()){auto T=q.top();q.pop();int dist=T.y.x;int u=T.y.y;cnt[u]++;if(cnt[t]==k){return dist;}for(int i=h[u];~i;i=ne[i]){int j=e[i];if(cnt[j]>k){continue;}q.push({dist+w[i]+dis[j],{dist+w[i],j}});}}return -1;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);memset(h,-1,sizeof(h));memset(h2,-1,sizeof(h2));cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;add(h,a,b,c);add(h2,b,a,c);}cin>>s>>t>>k;dijkstral();if(s==t){k++;}int ans=astar();cout<<ans;
}

?這里附上一道例題，求次短路。。

算是A*的特殊情況了，去直接秒殺吧。

acwing：133. 第二短路

貝茜把家搬到了一個(gè)小農(nóng)場，但她常?；氐?FJ 的農(nóng)場去拜訪她的朋友。

貝茜很喜歡路邊的風(fēng)景，不想那么快地結(jié)束她的旅途，于是她每次回農(nóng)場，都會選擇第二短的路徑，而不像我們所習(xí)慣的那樣，選擇最短路。

貝茜所在的鄉(xiāng)村有?RR?條雙向道路，每條路都連接了所有的?NN?個(gè)農(nóng)場中的某兩個(gè)。

貝茜居住在農(nóng)場?11，她的朋友們居住在農(nóng)場?NN（即貝茜每次旅行的目的地）。

貝茜選擇的第二短的路徑中，可以包含任何一條在最短路中出現(xiàn)的道路，并且一條路可以重復(fù)走多次。

當(dāng)然第二短路的長度必須嚴(yán)格大于最短路（可能有多條）的長度，但它的長度必須不大于所有除最短路外的路徑的長度。

輸入格式

第一行包含兩個(gè)整數(shù)?NN?和?RR。

接下來?RR?行，每行包含三個(gè)整數(shù)?A,B,DA,B,D，表示農(nóng)場?AA?和農(nóng)場?BB?之間存在一條長度為?DD?的路。

輸出格式

輸出僅包含一個(gè)整數(shù)，表示從農(nóng)場?11?到農(nóng)場?NN?的第二短路的長度。

數(shù)據(jù)范圍

1≤R≤1051≤R≤105,
1≤N≤50001≤N≤5000,
1≤D≤50001≤D≤5000,
1≤A,B≤N1≤A,B≤N

輸入樣例：

4 4
1 2 100
2 4 200
2 3 250
3 4 100

輸出樣例：

450

#include<bits/stdc++.h>
using namespace std;
const int N=5010,M=4e5+10;
#define x first
#define y second
typedef pair<int,int>PII;
typedef pair<int,PII>PIII;
int h[N],e[M],ne[M],w[M],idx;
int dis[N];
bool st[N];
int cnt[N];
int n,m;void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstral()
{memset(dis,0x3f,sizeof(dis));priority_queue<PII,vector<PII>,greater<PII>>q;q.push({0,n});dis[n]=0;while(q.size()){auto t=q.top();q.pop();int v=t.y;if(st[v]){continue;}st[v]=true;for(int i=h[v];~i;i=ne[i]){int j=e[i];if(st[j]){continue;}if(dis[j]>dis[v]+w[i]){dis[j]=dis[v]+w[i];q.push({dis[j],j});}}}
}
int astar(){int flag=0;priority_queue<PIII,vector<PIII>,greater<PIII>>q;q.push({dis[1],{0,1}});while(q.size()){auto t=q.top();q.pop();int v=t.y.y;int dist=t.y.x;cnt[v]++;if(cnt[n]==1){flag=dist;}if(cnt[n]>=2&&dist>flag){return dist;}for(int i=h[v];~i;i=ne[i]){int j=e[i];if(cnt[j]>2){continue;}q.push({dist+dis[j]+w[i],{dist+w[i],j}});}}
}
int main()
{ios::sync_with_stdio(0);cout.tie(0),cin.tie(0);memset(h,-1,sizeof(h));cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);add(b,a,c);}dijkstral();int ans=astar();cout<<ans;
}

?