본문 바로가기

알고리즘 관련/UVaOJ

UVaOJ)12878 Flowery Trails

문제:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4743


그래프에서 0번 정점에서 n-1번 정점으로의 여러경로의 최단거리에 속한 간선들의 가중치의 합을 구하는 문제이다.


한 정점에서 한 정점으로의 최단거리가 유일하다면 경로의 가중치의 합을 구하는건 그렇게 어렵지 않게 풀 수 있다.


하지만 최단거리가 여러가지 경로가 있다면 다익스트라를 이용할 시 그걸 구하는 시간만해도 꽤 오랜 시간이 걸릴 수 있다.


처음 문제를 접근할 때 다익스트라를 돌리며 일일이 경로를 다 저장하여 역추적을 하여 tle를 받게되었다.


하지만 잘 생각해본다면 다익스트라(혹은 spfa) 두번의 전처리로 문제를 해결해줄 수 있다.


우선 0번 정점에서 다익스트라로 모든 정점간의 거리 dist를 구하고


다시 n-1번 정점에서 다익스트라로 모든 정점간의 거리 backdist를 구한다.


이 후 모든 간선(u,v,g)에 대하여 dist[u]+g+backdist[v] == dist[n-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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n, m, x, y, z, dist[10010], bdist[10010], r;
vector<vector<pair<intint>>> vt;
void spfa(int s, int *d) {
    vector<int> v(n + 10);
    queue<int> qu;
    v[s] = 1;
    qu.push(s);
    d[s] = 0;
    while (qu.size()) {
        int here = qu.front();
        qu.pop();
        v[here] = 0;
        for (auto next : vt[here]) {
            if (d[next.first] > d[here] + next.second) {
                d[next.first] = d[here] + next.second;
                if (!v[next.first]) {
                    v[next.first] = 1;
                    qu.push(next.first);
                }
            }
        }
    }
}
int main() {
    freopen("input.txt""r", stdin);
    while (scanf("%d%d"&n, &m) != EOF) {
        vt.clear();
        vt.resize(n + 1);
        r = 0;
        memset(dist, 0x3fsizeof(dist));
        memset(bdist, 0x3fsizeof(bdist));
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d"&x, &y, &z);
            vt[x].push_back({ y,z });
            vt[y].push_back({ x,z });
        }
        spfa(0, dist), spfa(n - 1, bdist);
        int distance = dist[n - 1];
        for (int i = 0; i < n; i++) {
            for (auto next : vt[i]) {
                if (dist[i] + next.second + bdist[next.first] == distance)
                    r += next.second;
            }
        }
        printf("%d\n"* r);
    }
    return 0;
}
cs


'알고리즘 관련 > UVaOJ' 카테고리의 다른 글

UVaOJ)11765 Component Placement  (0) 2017.06.27
UVaOJ)12159 Gun Fight  (0) 2017.06.27
UVaOJ)10968 KuPellaKeS  (0) 2017.06.20
UVaOJ)12645 Water Supply  (0) 2017.06.19
UVaOJ)11751 Installing Diagnostic Software  (0) 2017.06.19