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]이 성립하면 그 간선은 최단거리의 경로에 속한 간선이다.

조금만 생각해보면 정당성을 증명하는건 어렵지 않다.

#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<int, int>>> vt;
void spfa(int s, int *d) {
    vector<int> v(n + 1, 0);
    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, 0x3f, sizeof(dist));
        memset(bdist, 0x3f, sizeof(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", 2 * r);
    }
    return 0;
}