1046. Shortest Distance

发表于 分类于 ， 阅读次数： 本文字数： 156 阅读时长 ≈ 1 分钟

#题意

仅由一个环的图, 求任意两个节点之间的最短距离

#思路

将环剪开成一条线, 记录每个节点距离起始节点的距离, 查询时取两个方向的距离的最小值

#感想

意外的很简单

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
#include <iostream>
using namespace std;

int D[100001];

int main()
{
#ifdef _DEBUG
    freopen(__FILE__ ".txt", "r", stdin);
#endif

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int dist;
        cin >> dist;
        D[i + 1] = D[i] + dist;
    }

    int len = D[n];

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        if (x > y) {
            swap(x, y);
        }
        cout << min(D[y - 1] - D[x - 1], len - D[y - 1] + D[x - 1]) << endl;
    }

    return 0;
}