计蒜客-迷阵突围
蒜头君陷入了坐标系上的一个迷阵,迷阵上有 n 个点,编号从 1 到 n。蒜头君在编号为 1 的位置,他想到编号为 n 的位置上。蒜头君当然想尽快到达目的地,但是他觉得最短的路径可能有风险,所以他会选择第二短的路径。现在蒜头君知道了 n 个点的坐标,以及哪些点之间是相连的,他想知道第二短的路径长度是多少。
注意,每条路径上不能重复经过同一个点。
输入格式
第一行输入两个整数 n (1≤n≤200) 和 m,表示一共有 n 个点和 m 条边。
接下来输入 n 行,每行输入两个整数 x_i, y_i(−500≤ x_i, y_i ≤500),代表第 i 个点的坐标。
接下来输入 m 行,每行输入两个整数 p_j, q_j (1≤ p_j, q_j ≤n),表示点 p_j和点 q_j 之间相连。
输出格式
输出一行,输出包含一个数,表示第二短的路径长度(小数点后面保留两位),如果第一短路径有多条,则答案就是第一最短路径的长度;如果第二最短路径不存在,则输出 -1−1。
样例输入
3 3
1 1
2 2
3 2
1 2
2 3
1 3
样例输出
2.41
分析
不可以重复经过点的次短路: 枚举两个顶点之间最短路上的每条边,每次在去掉这条边的剩下的图中计算最短路,取其中最小的一个答案就是最终次短路的答案。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
const double INF = 1e20;
const int N = 201;
double mp[N][N];
double dis[N];
bool vis[N];
int pre[N]; //用来记录最短路中每一个结点的前驱
int tmp[N];
typedef pair<int, int> PII;
set<PII, less<PII> > min_heap;
int n, m;
int x[N];
int y[N];
double distance(int a, int b) {
return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
}
bool dijstra(int u) {
for (int i = 1; i <= n; i++) {
dis[i] = INF;
}
memset(vis, false, sizeof vis);
memset(pre, -1, sizeof pre);
dis[u] = 0.0;
min_heap.insert(make_pair(0.0, u));
for (int i = 0; i < n; i++) {
if (min_heap.size() == 0) {
return false;
}
set<PII, less<PII> >::iterator it = min_heap.begin();
int min_v = it->second;
vis[min_v] = true;
min_heap.erase(*it);
for (int i = 1; i <= n; i++) {
if (!vis[i] && dis[i] > dis[min_v] + mp[min_v][i]) {
pre[i] = min_v; // 记录前驱
min_heap.erase(make_pair(dis[i], i));
dis[i] = dis[min_v] + mp[min_v][i];
min_heap.insert(make_pair(dis[i], i));
}
}
}
return true;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
mp[i][j] = INF;
}
}
int u, v;
for (int i = 0; i < m; i++) {
cin >> u >> v;
mp[u][v] = mp[v][u] = distance(u, v);
}
if (dijstra(1) == false) {
cout << -1 << endl;
return 0;
}
for (int i = 1; i <= n; i++) { // 因为 pre[i] 会被后面的 dijstra() 操作重新覆盖
tmp[i] = pre[i];
}
double ans = INF;
int now = n;
//枚举两个顶点之间最短路上的每条边,每次在去掉这条边的剩下的图中计算最短路
while (tmp[now] + 1) { //因为 tmp[起始点] = -1, 当now = 起始点时,就会停止循环
mp[now][tmp[now]] = mp[tmp[now]][now] = INF; //去掉这条边
dijstra(1);
ans = min(ans, dis[n]); //取其中最小的一个答案就是最终次短路的答案
mp[now][tmp[now]] = mp[tmp[now]][now] = distance(now, tmp[now]); //还原这条边,以进行下一个
now = tmp[now];
}
if (ans == INF) {
cout << -1 << endl;
} else {
printf("%.2lf", ans);
}
return 0;
}