VOJ 迷阵突围 题解 次短路径 dijkstra算法

迷阵突围

题目描述

小明陷入了坐标系上的一个迷阵，迷阵上有 n 个点，编号从 1 到 n 。小明在编号为 1 的位置，他想到编号为 n 的位置上。小明当然想尽快到达目的地，但是他觉得最短的路径可能有风险，所以他会选择第二短的路径。现在小明知道了 n 个点的坐标，以及哪些点之间是相连的，他想知道第二短的路径长度是多少。

注意，每条路径上不能重复经过同一个点。

输入描述

第一行输入两个整数 n ( $1\le n\le 200$ ) 和 m ，表示一共有 n 个点和 m 条边。
接下来输入 n 行，每行输入两个整数 $x_i$，$y_i$( $-500\le x_i$，$y_i\le 500$ )，代表第 $i$ 个点的坐标。
接下来输入 m 行，每行输入两个整数 $p_j$，$q_j$( $1\le p_j$，$q_j\le n$ )，表示点 $p_j$ 和点 $q_j$ 之间相连。

输出描述

输出一行，输出包含一个数，表示第二短的路径长度（小数点后面保留两位），如果第一短路径有多条，则答案就是第一最短路径的长度；如果第二最短路径不存在，则输出 −1 。

样例 #1

样例输入 #1

3 3
1 1
2 2
3 2
1 2
2 3
1 3

样例输出 #1

2.41

思路

求次短路径长度分为两种：一种是可以重复经过一个点的，另一种是不能重复经过一个点的。前者解题策略是用dis1和dis2分别记录最短路长度和次短路长度，并在更新过程中依次判断是否需要更新最短路和次短路；后者解题策略是先统计出最短路径所经过的所有边，然后枚举所有经过的边，在去掉该边的情况下重新求出最短路径长度，并用ans记录重新求出的n个新图上最短路径长度中最小的那个，即为原图上的次短路径长度。对于本题，题目明确说明属于后者。注意，当最短路径不存在时，需要特判，此时次短路径一定不存在，输出 -1。

代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef long long ll;const int maxn = 1e5 + 6;
const int maxm = 1e5 + 6;struct edge
{int to;     // to为边的指向double len; // len为边的长度即边权
};vector<edge> e[maxn]; // 存储以点i为起点的边struct node
{double dis;                         // dis为目前到该点的最短路长度int num;                            // num为该点序号bool operator>(const node &a) const // 小根堆中的大于号重载{return dis > a.dis;}
};double minDis[maxn]; // 从起点到第i个点的最短路长度
bool vis[maxn];      // 第i个点是否已确定最短路长度
int pre[maxn];
int x, y; // 记录去掉的边的起点x和终点yvoid dijkstra(int n, int s) // n为点的个数，s为起点
{priority_queue<node, vector<node>, greater<node>> pq; // 还未确定最短路长度的点存放在小根堆中// 将最短路距离初始化为无穷大，vis初始化为0for (int i = 1; i <= n; i++){minDis[i] = 1e10;vis[i] = 0;}minDis[s] = 0.0; // 起点到起点的最短路长度为0pq.push({0, s});while (!pq.empty()){int u = pq.top().num; // 有向边的起点pq.pop();if (vis[u]) // 若该点已确定最短路长度，跳过continue;vis[u] = 1;for (edge eg : e[u]) // 遍历以该点为起点的所有有向边{int v = eg.to;if (x == u && y == v) // 遍历到去掉的边就跳过，从而找到次短路径continue;double w = eg.len;if (minDis[v] > minDis[u] + w) // 更新最短路长度{minDis[v] = minDis[u] + w;pre[v] = u; // 用pre记录最短路径中v的前驱upq.push({minDis[v], v});}}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);// 问题转化为求根1到各个结点的最短路径长度int n, m, s; // 点的个数，有向边的个数，出发点的编号cin >> n >> m;vector<pair<int, int>> a(n + 1); // 点的坐标for (int i = 1; i <= n; i++){cin >> a[i].first >> a[i].second;pre[i] = i;}s = 1; // 起点为根结点int u, v;double w;while (m--){cin >> u >> v;// 在读入无向边的过程中计算每条边的边权，即两点间距离w = sqrt(pow((a[u].first - a[v].first), 2) + pow((a[u].second - a[v].second), 2));e[u].push_back({v, w});e[v].push_back({u, w});}dijkstra(n, s);if (pre[n] == n) // 如果不存在最短路径，那么一定不存在次短路径{cout << -1 << '\n';return 0;}vector<pair<int, int>> path;int tmp = n;while (tmp != 1) // 通过从n向1遍历前驱，即可找出完整的路径{path.push_back({pre[tmp], tmp});tmp = pre[tmp];}double ans = 1e10;for (int i = 0; i < path.size(); i++) // 枚举路径上所有的边，统计去掉该边后的新图上最短路径长度的最小值{x = path[i].first;y = path[i].second;dijkstra(n, s);ans = min(ans, minDis[n]);}if (ans == 1e10) // 如果不存在次短路径，输出-1{cout << -1 << '\n';}else{cout << fixed << setprecision(2) << ans << '\n';}return 0;
}