5944번: Apple Delivery

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

$O(C\lg P)$

답은 min((pb~pa1 최단 거리),(pb~pa2 최단 거리)) + (pa1~pa2 최단 거리)

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MXP = 1e5;
int c, p, pb, pa1, pa2, dis[MXP + 1];
vector<pair<int, int> > adj[MXP + 1];
void spath(int s) {
    fill(&dis[1], &dis[p + 1], 1e9);
    dis[s] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push({ 0,s });
    while (!pq.empty()) {
        int h = pq.top().second, d = -pq.top().first;
        pq.pop();
        if (dis[h] ^ d) continue;
        for (auto it : adj[h]) if (d + it.second < dis[it.first]) {
            dis[it.first] = d + it.second;
            pq.push({ -dis[it.first],it.first });
        }
    }
}
int main() {
    scanf("%d%d%d%d%d", &c, &p, &pb, &pa1, &pa2);
    for (int i = 0, x, y, z; i < c; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
    }
    spath(pa1);
    int t = dis[pa2];
    spath(pb);
    printf("%d", min(dis[pa1], dis[pa2]) + t);
    return 0;
}