zhanyeye's learning log

(^～^)

0%

计蒜客-迷阵突围

Posted on Edited on In

蒜头君陷入了坐标系上的一个迷阵，迷阵上有 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。

样例输入

1
2
3
4
5
6
7
3 3
1 1
2 2
3 2
1 2
2 3
1 3

样例输出

1
2.41

分析

不可以重复经过点的次短路: 枚举两个顶点之间最短路上的每条边，每次在去掉这条边的剩下的图中计算最短路，取其中最小的一个答案就是最终次短路的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#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;
}