9370번: Destination Unknown

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

각 목적지 후보마다 해당 지점까지의 최단 거리가 g와 h사이 도로를 거쳐가는 최단 거리와 같은지 판단하는 문제이다.
간단히 각 교차로마다 g와 h사이 도로를 지났는지의 여부에 따라 두 개의 노드를 만들어서 최단거리를 구해 비교하면 된다.

또는 노드를 두 개씩 만들지 않고 다음과 같은 트릭을 사용해서 풀 수도 있다.
1. 모든 도로의 길이를 2배로 만든다.
2. g와 h사이 도로 길이만 1 감소 시킨다.
3. 최단 경로를 구한 뒤, 후보 까지의 최단 거리가 홀수인 경우 목적지로 가능하다.

시간복잡도는 각 테스트 케이스마다 $O(m\lg n)$

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
void solve() {
    vector<pair<int, int> > adj[2001];
    int cst[2001], n, m, t, s, g, h, c[100];
    priority_queue<pair<int, int> > pq;
    scanf("%d%d%d%d%d%d", &n, &m, &t, &s, &g, &h);
    for (int i = 0, a, b, d; i < m; i++) {
        scanf("%d%d%d", &a, &b, &d);
        d *= 2;
        if (a*b == g*h&&a + b == g + h) d--;
        adj[a].push_back({ b,d });
        adj[b].push_back({ a,d });
    }
    fill(cst + 1, cst + 1 + n, 1e9);
    cst[s] = 0;
    pq.push({ 0,s });
    while (!pq.empty()) {
        int tdis = -pq.top().first, tpos = pq.top().second;
        pq.pop();
        if (tdis^cst[tpos]) continue;
        for (auto it : adj[tpos]) if (cst[it.first] > tdis + it.second) {
            cst[it.first] = tdis + it.second;
            pq.push({ -cst[it.first],it.first });
        }
    }
    for (int i = 0; i < t; i++) scanf("%d", c + i);
    sort(c, c + t);
    for (int i = 0; i < t; i++) if (cst[c[i]] & 1) printf("%d ", c[i]);
    puts("");
}
int main() {
    int T;
    for (scanf("%d", &T); T--;) solve();
    return 0;
}