문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 목적지로 가는 최단 경로에 특정 길이 포함되는지를 확인해야하는 문제이다.
  • s에서 x까지 가는 길 중에서 g와 h를 지나서 가는 최단 경로는 두가지이다.
  • s->g->h->x와 s->h->g->x 이렇게 두가지이다.
  • 이 두 경우를 찾기 위해서 g, h, s를 시작점으로 다익스트라를 진행하여 결과를 저장한다.
  • 이렇게 찾은 s->g->h->x나 s->h->g->x 값이 s->x와 같다면 이 친구는 벡터에 넣어서 sort해준 후 출력한다.

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define pii pair<int, int>
#define FOR(i,j) for(int i = 0; i < j; i++)

using namespace std;

char buf[1 << 17];

inline char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int N() {
    int sum = 0;
    bool flg = 1;
    char now = read();

    while (now == 10 || now == 32) now = read();
    if (now == '-') flg = 0, now = read();
    while (now >= 48 && now <= 57) {
        sum = sum * 10 + now - 48;
        now = read();
    }

    return flg ? sum : -sum;
}

int main(){
    int T, n, m, t, s, g, h, a, b, w, x;
    T = N();
    while(T--){
        n = N(), m = N(), t = N(), s = N(), g = N(), h = N();
        vector<vector<pii> > e(n + 1);
        while(m--){
            a = N(), b = N(), w = N();
            e[a].push_back({b, w});
            e[b].push_back({a, w});
        }
        vector<int> d;
        vector<int> to_g(n + 1);
        vector<int> to_h(n + 1);
        queue<int> q;        
        for(int i = 0; i < 3; i++){
            d = vector<int>(n+1, 20000000);
            if(i == 0) a = g;
            else if(i == 1) a = h;
            else a = s;
            d[a] = 0;
            q.push(a);
            while(!q.empty()){
                int top = q.front(); q.pop();
                FOR(i, e[top].size()){
                    int next = e[top][i].first, w = e[top][i].second;
                    if(d[next] > d[top] + w){
                        d[next] = d[top] + w;
                        q.push(next);
                    }
                }
            }
            if(i == 0)FOR(j, n + 1)to_g[j] = d[j];
            else if(i == 1)FOR(j, n + 1)to_h[j] = d[j];            
        }
        vector<int> ans;
        while(t--){
            x = N();
            if(to_g[s] + to_g[h] + to_h[x] == d[x]) ans.push_back(x);
            else if(to_h[s] + to_g[h] + to_g[x] == d[x]) ans.push_back(x);
        }
        sort(ans.begin(), ans.end());
        FOR(i, ans.size())printf("%d ", ans[i]);
        printf("\n");
    }
}

느낀점

  • ACM-ICPC 문제여서 상당히 긴장했는데 문제를 내 힘으로 풀 수 있었음에 만족한다.
  • 처음에 구상했던 방법대로 진행되지 않아서 아쉬웠지만 다음에 이런 유형을 더 조심스럽게 접근할 수 있을 것 같다!