SHARE
TWEET

Untitled

a guest Nov 19th, 2019 78 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. #define INF 100000000000000000
  5.  
  6. long long N, A, B, i, j, k, a, b, c, w, dist[10010], proc[10010], source, dest;
  7. vector<vector<pair<long long, long long>>> adj;
  8. priority_queue<pair<long long, long long>> q;
  9.  
  10. int main() {
  11.   ifstream cin("input.txt");
  12.   ofstream cout("output.txt");
  13.  
  14.   cin >> N >> A >> B;
  15.   source = 1;
  16.   dest = N;
  17.   for (i = 0; i <= A + B; i++) {
  18.     adj.push_back({});
  19.   }
  20.   for (i = 0; i < A; i++) {
  21.     cin >> a >> b;
  22.     adj[a].push_back({b, 0});
  23.     adj[b].push_back({a, 0});
  24.   }
  25.   for (i = 0; i < B; i++) {
  26.     cin >> a >> b;
  27.     adj[a].push_back({b, 1});
  28.     adj[b].push_back({a, 1});
  29.   }
  30.  
  31.   for (i = 1; i <= N; i++) {
  32.     dist[i] = INF;
  33.     proc[i] = 0;
  34.   }
  35.   dist[source] = 0;
  36.   q.push({0, source});
  37.  
  38.   while (!q.empty()) {
  39.     a = q.top().second;
  40.     q.pop();
  41.     if (proc[a] == 1) {
  42.       continue;
  43.     }
  44.     proc[a] = 1;
  45.     for (auto u : adj[a]) {
  46.       b = u.first;
  47.       w = u.second;
  48.       if (dist[a] + w < dist[b]) {
  49.         dist[b] = dist[a] + w;
  50.         q.push({-dist[b], b});
  51.       }
  52.     }
  53.   }
  54.  
  55.   cout << dist[dest];
  56.  
  57.   return 0;
  58. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top