10652번: Piggy Back

https://www.acmicpc.net/problem/10652

$O(n+m)$

1,2,n번 지점으로부터 나머지 지점까지의 최단 시간을 BFS를 통해 모두 구해 놓는다.
어떤 지점으로부터 1,2,n까지 최단 시간 합의 최솟값을 출력한다.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MXN = 4e4;
int b, e, p, n, m, dis[3][MXN + 1], res = 2e9;
vector<int> adj[MXN + 1];
void bfs(int h, int t) {
    queue<int> q;
    q.push(h); dis[t][h] = 1;
    while (!q.empty()) {
        for (auto it : adj[q.front()]) if (!dis[t][it]) {
            dis[t][it] = dis[t][q.front()] + 1;
            q.push(it);
        }
        q.pop();
    }
}
int main() {
    scanf("%d%d%d%d%d", &b, &e, &p, &n, &m);
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    bfs(1, 0);
    bfs(2, 1);
    bfs(n, 2);
    for (int i = 1; i <= n; i++) res = min(res, dis[0][i] * b + dis[1][i] * e + dis[2][i] * p);
    printf("%d", res - b - e - p);
    return 0;
}