9370, 삐빅-- 메모리 초괍니다(다익스트라로 최단경로 tree)

9370번: 미확인 도착지

 

#include <bits/stdc++.h>
#define endl "\n" // don't use when you cover interactive problem
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti;
 
const int INF = 2e6;
int n, m, t, start, g, h;
 
void dijkstra(map<int, vector<pi> >& edge, vector<int>& dp, map<int, vector<int> >& shortest, int start)
{
    priority_queue<ti, vector<ti>, greater<ti> > pq;
    pq.push({0, start, -1}); // weight, des, parent
    while(!pq.empty()){
        auto [dist, cur, parent] = pq.top(); pq.pop();
        // 각 노드에 대해 최초로 heap 에서 나올때가 최단경로
 
        if(dp[cur] < dist) continue;
        // 따라서 각 노드에 대해 이미 heap에서 나온적 있다면 dp[cur] 값은 이미 최단경로로 저장되었을 것
        shortest[parent].emplace_back(cur);
        if(dp[cur] == dist) continue;
        // 각 노드에 대해 dp[cur] 가 이미 최단경로라면 앞서 그 노드와 인접한 edge 는 rest 과정을 거쳤을 것이므로 생략
        dp[cur] = dist;
 
        for(auto [w, nex]: edge[cur]){
            int nex_dist = dist + w;
            if(nex_dist <= dp[nex]){ // < 가 아닌 등호까지 포함하므로써 가중치가 같은 최단경로 모두 구함
                pq.push({nex_dist, nex, cur});
            }
        }
    }
}
 
void check(map<int, bool>& des, int tar) // target 이 목적지 중 하나이면 방문표시
{
    if(des.find(tar) != des.end()) des[tar] = true;
}
 
void bfs(map<int, vector<int> >& shortest, map<int, bool>& des, int start)
{
    queue<int> q;
    q.push(start);
    check(des, start);
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        for(auto nex: shortest[cur]){
            q.push(nex);
            check(des, nex);
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while(T--){
        cin >> n >> m >> t >> start >> g >> h;
        map<int, vector<pi> > edge; // dep -> (weight, des)
        loop(i, m){
            int a, b, d; cin >> a >> b >> d;
            edge[a].emplace_back(d, b);
            edge[b].emplace_back(d, a);
        }
        map<int, bool> des; // node -> isvisited?
        loop(i, t){
            int x; cin >> x;
            des[x] = false;
        }
 
        vector<int> dp(n+1, INF);
        map<int, vector<int> > shortest; // 출발지로 각 노드를 방문하는 최단경로 tree
        dijkstra(edge, dp, shortest, start); // 다익스트라 알고리즘을 시행하면서 최단경로 tree 'shortest'를 만듬
 
 
        // shortest 를 bfs 로 순회하면서 목적지 des 가 나오면 방문표시
        if(find(all(shortest[g]), h) != shortest[g].end()) bfs(shortest, des, h);
        // shortest에서 g가 h의 parent 인 경우
        if(find(all(shortest[h]), g) != shortest[h].end()) bfs(shortest, des, g);
        // shortest에서 h가 g의 parent 인 경우
 
        for(auto [node, isvisited]: des){
            if(isvisited) cout << node << ' ';
        }
        cout << endl;
    }
 
    return 0;
}