티스토리 뷰

알고리즘 관련/UVaOJ

UVaOJ)12878 Flowery Trails

JASON 자손9319 2017. 6. 23. 16:36

문제: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)12878 Flowery Trails  (0) 2017.06.23
UVaOJ)10968 KuPellaKeS  (0) 2017.06.20
UVaOJ)12645 Water Supply  (0) 2017.06.19
UVaOJ)11751 Installing Diagnostic Software  (0) 2017.06.19
TAG
댓글
댓글쓰기 폼