문제 바로가기

문제

예술가가 도시의 거리들을 이동하고 있고, 목적지의 후보가 여러개 있다. 예술가는 목적지로 갈때 최단 경로로 이동한다.

이때 예술가가 지나간 거리 하나를 알 때(냄새를 맡은 길) 목적지 후보들 중 가능한 지점을 출력한다.

ex) 아래 그림과 같을때 (1번에서 출발)

3번으로의 최단거리에는 초록색 길이 없으므로 x

4번으로의 최단거리에는 초록색 길이 포함되므로 o

5번으로의 최단거리는 초록 길이 없는, 있는 두가지인데 이때도 가능하다고 본다.

조건

  • 2 ≤ 교차로(정점) ≤ 2000
  • 1 ≤ 도로(간선) ≤ 50000
  • 1 ≤ 목적지 후보 ≤ 100
  • 두개의 정점 사이에는 도로가 최대 1개 존재한다.

설계

다익스트라를 진행하며 냄새를 맡은 길을 지나가면 체크한다.

이때 passed[v]를 정점 v까지 최단거리로 올때 냄새를 맡은 길을 지났는지에 대한 여부라고 하고,

현재 최단거리를 갱신하면서 a→b로 진행할 때

if ((a<->b == 냄새를 맡은 경로) || passed[a])
    passed[b] = true;
else if (갱신전거리 > cur.second + p.second)
	  passed[b] = false;

if문에서는 현재 지나는 경로가 냄새를 맡은 경로이거나, a까지 오면서 냄새를 맡은 경로를 지났으면 b로 갈때도 냄새를 맡은 경로를 지나게 되므로 passed[b] = true로 바꿔준다.

if에 걸리지 않고 만약 원래 최단거리가 새로운 최단거리보다 크면 최단거리로 갈때 냄새를 맡은 경로를 지나지 않기 때문에 passed[b] = false로 해 주어야 한다. (이때 ≥이 아니라 >를 쓴 이유는 최단거리로 가는 경우가 여러개이면 paseed[b]에 대한 값이 바뀌지 않아야 하기 때문이다.)

구현

C++ 코드 보기 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define INF 987654321

struct comp {
    bool operator() (pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    }  
};

int dist[2001];

int main() {
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        int n, m, t, s, g, h;
        vector<int> to;
        vector<pair<int, int>> edge[2001];
        bool passed[2001] = { false,};

        cin >> n >> m >> t >> s >> g >> h;
        for (int i = 1; i <= n; i++) {
            dist[i] = INF;
        }
        dist[s] = 0;
        int _g = g, _h = h;
        g = min(_g, _h);
        h = max(_g, _h);

        for (int i = 0; i < m; i++) {
            int a, b, d;
            cin >> a >> b >> d;
            edge[a].push_back({b, d});
            edge[b].push_back({a, d});
        }
        
        for (int i = 0; i < t; i++) {
            int num;
            cin >> num;

            to.push_back(num);
        }

        
        priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
        pq.push({s, 0});

        while (!pq.empty()) {
            auto cur = pq.top(); //first: now node, second: now dist
            pq.pop();
            if (cur.second > dist[cur.first]) continue;

            for (auto p: edge[cur.first]) { //p-> first: to edge, second: weight
                if (dist[p.first] >= cur.second + p.second) {
                    int beforeDist = dist[p.first];
                    dist[p.first] = cur.second + p.second;
                    if (beforeDist > cur.second + p.second)
                        pq.push({p.first, dist[p.first]});
                    //p.first와 cur.first 가 g와 h이면
                    if ((g == min(p.first, cur.first) && h == max(p.first, cur.first)) || passed[cur.first]) {
                        passed[p.first] = true;
                    }
                    else if (beforeDist > cur.second + p.second)
                        passed[p.first] = false;
                }
            }
        }

        sort(to.begin(), to.end());
        for (auto i: to) {
            if (passed[i]) cout << i << " ";
        }
        cout << endl;
    }

    return 0;
}