[Acwing] 178. 第K短路 A*

前言

传送门 :

思路

1. 建立返图,从终点跑一遍所有点的最短路,将这个最短路作为其他点的估价函数
2. 然后从 S S S开始拓展,每次取出估价函数的最小值,将能扩展的点全部扩展。 估 计 值 = 真 实 距 离 + 估 价 函 数 估计值 = 真实距离+估价函数 估计值=真实距离+估价函数
3. 当 S S S遇到 K K K次 T T T的时候,就求出了 S − T S-T S−T的第 K K K短路

Code

// Problem: 第K短路
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/180/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;
const int N = 1010;

struct node{
	int to,val;
};
vector g[N],rg[N];
int n,m;
int S,T,K;
int dist[N],st[N];
int cnt[N];

void dij(){
	memset(dist,0x3f,sizeof dist);
	 priority_queue q;
	 dist[T] = 0 ;

	 q.push({0,T});
	 while(q.size()){
			pii t = q.top();
	        q.pop();

	        int num = t.y;  //表示节点编号和到终点的距离

	        if(st[num]) continue;
	         st[num] = true;   //节点编号为j的节点被确定了最短距离

	        //用num节点更新全图的dist距离
	        for(auto j :  rg[num]){
	    	      if(dist[num] + j.val n>>m;
	for(int i=1;i>a>>b>>c;
		g[a].pb({b,c});
		rg[b].pb({a,c});
	}
	cin>>S>>T>>K;

	//因为起点==终点 所以D[S->S] = 0  因此第K大变为K+1大
	if(S == T) K ++;

	dij();
	cout