10853번: Change of Scenery

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


$O(m\lg n)$

최단 경로의 개수를 세어 2개 이상이면 가능하고 아니면 불가능하다.

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int n, m, k, cst[10001], cnt[10001];
vector<pair<int, int> > adj[10001];
priority_queue<pair<int, int> > pq;
int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (k--) scanf("%*d");
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
    }
    fill(cst + 2, cst + 1 + n, 1e9);
    pq.push({ 0,1 }); cnt[1] = 1;
    while (!pq.empty()) {
        int h = pq.top().second, dis = -pq.top().first;
        pq.pop();
        if (cst[h] ^ dis) continue;
        if (cnt[h] > 2) cnt[h] = 2;
        for (auto it : adj[h]) {
            int tdis = it.second + dis;
            if (tdis < cst[it.first]) {
                cst[it.first] = tdis;
                cnt[it.first] = 0;
                pq.push({ -tdis,it.first });
            }
            if (tdis == cst[it.first]) cnt[it.first] += cnt[h];
        }
    }
    puts(cnt[n] - 1 ? "yes" : "no");
    return 0;
}