Advertisement
mickypinata

TUMSO18: Zombie Land

Jul 23rd, 2021
1,032
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5. typedef pair<int, int> pii;
  6. typedef pair<lli, int> pli;
  7.  
  8. const int N = 2e5;
  9.  
  10. vector<pii> adj[N + 1];
  11. lli dist[2][N + 1], dist2[N + 1];
  12. bool visited[N + 1];
  13. int nVertex;
  14.  
  15. void dijkstra(int i, int st){
  16.     for(int u = 1; u <= nVertex; ++u){
  17.         visited[u] = false;
  18.         dist[i][u] = 1e18;
  19.     }
  20.     priority_queue<pli, vector<pli>, greater<pli>> pq;
  21.     dist[i][st] = 0;
  22.     pq.emplace(dist[i][st], st);
  23.     while(!pq.empty()){
  24.         int u = pq.top().second;
  25.         pq.pop();
  26.         if(visited[u]){
  27.             continue;
  28.         }
  29.         visited[u] = true;
  30.         for(pii p : adj[u]){
  31.             int v = p.first;
  32.             int w = p.second;
  33.             if(!visited[v] && dist[i][u] + w < dist[i][v]){
  34.                 dist[i][v] = dist[i][u] + w;
  35.                 pq.emplace(dist[i][v], v);
  36.             }
  37.         }
  38.     }
  39. }
  40.  
  41. int main(){
  42.  
  43.     int nEdge, st, ed;
  44.     scanf("%d%d%d%d", &nVertex, &nEdge, &st, &ed);
  45.     for(int i = 1; i <= nEdge; ++i){
  46.         int u, v, w;
  47.         scanf("%d%d%d", &u, &v, &w);
  48.         adj[u].emplace_back(v, w);
  49.         adj[v].emplace_back(u, w);
  50.     }
  51.     dijkstra(0, st);
  52.     dijkstra(1, ed);
  53.     priority_queue<pli, vector<pli>, greater<pli>> pq;
  54.     for(int i = 1; i <= nVertex; ++i){
  55.         dist2[i] = 1e18;
  56.         visited[i] = false;
  57.     }
  58.     lli stPath = dist[0][ed];
  59.     for(int i = 1; i <= nVertex; ++i){
  60.         if(dist[0][i] + dist[1][i] == stPath){
  61.             dist2[i] = 0;
  62.             pq.emplace(dist2[i], i);
  63.         }
  64.     }
  65.     while(!pq.empty()){
  66.         int u = pq.top().second;
  67.         pq.pop();
  68.         if(visited[u]){
  69.             continue;
  70.         }
  71.         visited[u] = true;
  72.         for(pii p : adj[u]){
  73.             int v = p.first;
  74.             int w = p.second;
  75.             if(!visited[v] && dist2[u] + w < dist2[v]){
  76.                 dist2[v] = dist2[u] + w;
  77.                 pq.emplace(dist2[v], v);
  78.             }
  79.         }
  80.     }
  81.     int Q;
  82.     scanf("%d", &Q);
  83.     while(Q--){
  84.         int u;
  85.         scanf("%d", &u);
  86.         cout << dist2[u] << '\n';
  87.     }
  88.  
  89.     return 0;
  90. }
  91.  
Advertisement
RAW Paste Data Copied
Advertisement