K短路：最短路是1短路，次短路是2短路，以此类推得到K短路。
算法流程：
反向建图，从终点求解一次单源最短路。正向建图，从起点开始进行A*搜索，其中启发式函数为，其中 f 表示分数，g 表示走到该点用到的最短路程，h 表示还需要走最少 h 路程才能到达终点。那么在A*搜索的过程中第K此到达终点的路就是K短路。配题：HDU 6181
题意：无向图中求次短路，也就是 2短路问题。
#include<iostream> #include<cstring> #include<queue> #include<cstdio> #include<vector> #define inf 1e17+7 using namespace std; const int maxn = 100000+5; const int maxm = 100000+5; int n, m; struct NODE { int v; long long int w; }; struct queue_NODE { int v; long long int f, g; bool operator< (const queue_NODE& x)const { if (x.f == f) { return x.g < g; } else { return x.f < f; } } }; vector<NODE>graph[maxn]; long long int dis[maxn]; void spfa(int source, int sink) { bool vis[maxn]; queue<int>q; while (!q.empty()) q.pop(); memset(vis, false, sizeof(vis)); for (int i = 1; i <= n; i++) { dis[i] = inf; } dis[source] = 0; vis[source] = true; q.push(source); while (!q.empty()) { int cur_node = q.front(); q.pop(); vis[cur_node] = false; for (int i = 0; i < graph[cur_node].size(); i++) { int next_node = graph[cur_node][i].v; long long int w = graph[cur_node][i].w; if (dis[next_node] > dis[cur_node] + w) { dis[next_node] = dis[cur_node] + w; if (vis[next_node] == false) { vis[next_node] = true; q.push(next_node); } } } } } long long int A_star(int source, int sink, int k) { if (dis[source] == inf) return -1; queue_NODE cur_node; priority_queue<queue_NODE>q; while (!q.empty()) q.pop(); int cnt = 0; if (source == sink) ++cnt; q.push(queue_NODE{source, dis[source], 0}); while (!q.empty()) { cur_node = q.top(); q.pop(); if (cur_node.v == sink) ++cnt; if (cnt == k) return cur_node.g; for (int i = 0; i < graph[cur_node.v].size(); i++) { int next_node = graph[cur_node.v][i].v; long long int w = graph[cur_node.v][i].w; long long int g = cur_node.g + w; long long int f = g + dis[next_node]; q.push(queue_NODE{next_node, f, g}); } } return -1; } int main() { int T; cin>> T; while (T--) { cin>> n>> m; for (int i = 1; i <= n; i++) { graph[i].clear(); } for (int i = 1; i <= m; i++) { int a, b; long long int w; cin>> a>> b>> w; graph[a].push_back(NODE{b, w}); graph[b].push_back(NODE{a, w}); } spfa(n, 1); cout<< A_star(1, n, 2)<< endl; } return 0; }
