YEZAELP

PROG-1133: รถไฟใต้ดิน (subway)

Mar 21st, 2021 (edited)
118
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.96 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1000010;
  6. const int M = 510;
  7. const int INF = 2e9;
  8. using pii = pair <int, int>;
  9. int n, m;
  10. vector <int> station[N], line[M], g[M];
  11. vector < vector <int>> dis(M, vector <int> (M, INF));
  12. vector < vector <bool>> visited(M, vector <bool> (M, false));
  13. bool check[M][M];
  14.  
  15. int main(){
  16.  
  17.     scanf("%d%d", &n, &m);
  18.  
  19.     for(int i=1;i<=m;i++){
  20.         int S;
  21.         scanf("%d", &S);
  22.         for(int j=1;j<=S;j++){
  23.             int si;
  24.             scanf("%d", &si);
  25.             line[i].push_back(si);
  26.             station[si].push_back(i);
  27.         }
  28.     }
  29.  
  30.     for(int u=1;u<=m;u++){ // line
  31.         for(auto si: line[u]){ // station
  32.             for(auto i: station[si]){ // line
  33.                 if(u == i or check[u][i] or check[i][u]) continue;
  34.                 check[u][i] = true;
  35.                 check[i][u] = true;
  36.                 g[i].push_back(u);
  37.                 g[u].push_back(i);
  38.             }
  39.         }
  40.     }
  41.  
  42.     for(int i=1;i<=m;i++){
  43.         int li = i;
  44.         queue <pii> q;
  45.         dis[li][li] = 0;
  46.         q.push({0, li});
  47.         while(!q.empty()){
  48.             int u, d;
  49.             u = q.front().second;
  50.             d = q.front().first;
  51.             q.pop();
  52.             if(visited[li][u])
  53.                 continue;
  54.             visited[li][u] = true;
  55.             for(auto v: g[u]){
  56.                 if(!visited[li][v] and d + 1 < dis[li][v]){
  57.                     dis[li][v] = d + 1;
  58.                     q.push({d+1, v});
  59.                 }
  60.             }
  61.         }
  62.     }
  63.  
  64.     int Q;
  65.     scanf("%d", &Q);
  66.     while(Q--){
  67.         int a, b;
  68.         scanf("%d%d", &a, &b);
  69.         int ans = INF;
  70.         for(auto sta: station[a]){
  71.             for(auto stb: station[b]){
  72.                 ans = min(ans, dis[sta][stb]);
  73.             }
  74.         }
  75.         if(ans >= INF) printf("impossible");
  76.         else printf("%d", ans);
  77.         printf("\n");
  78.     }
  79.  
  80.     return 0;
  81. }
  82.  
RAW Paste Data Copied