迷阵突围
题目描述
小明陷入了坐标系上的一个迷阵,迷阵上有 n 个点,编号从 1 到 n 。小明在编号为 1 的位置,他想到编号为 n 的位置上。小明当然想尽快到达目的地,但是他觉得最短的路径可能有风险,所以他会选择第二短的路径。现在小明知道了 n 个点的坐标,以及哪些点之间是相连的,他想知道第二短的路径长度是多少。
注意,每条路径上不能重复经过同一个点。
输入描述
第一行输入两个整数 n ( 1 ≤ n ≤ 200 1 ≤ n ≤ 200 1≤n≤200 ) 和 m ,表示一共有 n 个点和 m 条边。
接下来输入 n 行,每行输入两个整数 x i x_i xi, y i y_i yi( − 500 ≤ x i −500 ≤ x_i −500≤xi, y i ≤ 500 y_i ≤ 500 yi≤500 ),代表第 i i i 个点的坐标。
接下来输入 m 行,每行输入两个整数 p j p_j pj, q j q_j qj( 1 ≤ p j 1 ≤ p_j 1≤pj, q j ≤ n q_j ≤ n qj≤n ),表示点 p j p_j pj 和点 q j q_j qj 之间相连。
输出描述
输出一行,输出包含一个数,表示第二短的路径长度(小数点后面保留两位),如果第一短路径有多条,则答案就是第一最短路径的长度;如果第二最短路径不存在,则输出 −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和终点y
void dijkstra(int n, int s) // n为点的个数,s为起点
{
priority_queue<node, vector<node>, greater<node>> pq; // 还未确定最短路长度的点存放在小根堆中
// 将最短路距离初始化为无穷大,vis初始化为0
for (int i = 1; i <= n; i++)
{
minDis[i] = 1e10;
vis[i] = 0;
}
minDis[s] = 0.0; // 起点到起点的最短路长度为0
pq.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的前驱u
pq.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;
}