danielvitor23

C

Aug 28th, 2023
1,475
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. using namespace std;
  5. using i64 = long long;
  6. using ii = pair<i64, i64>;
  7. const int INF = 0x3f3f3f3f;
  8.  
  9. int n, m, k;
  10. vector<int> wormholes;
  11. vector<vector<int>> gr;
  12.  
  13. void bfs(int s, vector<int> &d) {
  14.   queue<int> q;
  15.   d[s] = 0;
  16.   q.push(s);
  17.   while (!q.empty()) {
  18.     int u = q.front(); q.pop();
  19.     for (int to : gr[u]) if (d[to] == INF) {
  20.       d[to] = d[u] + 1;
  21.       q.push(to);
  22.     }
  23.   }
  24. }
  25.  
  26. ii normalize(ii a) {
  27.   i64 g = __gcd(a.fi, a.se);
  28.   a.fi /= g;
  29.   a.se /= g;
  30.   return a;
  31. }
  32.  
  33. ii sum(ii a, ii b) {
  34.   a = normalize(a);
  35.   b = normalize(b);
  36.   i64 lcm = a.se / __gcd(a.se, b.se) * b.se;
  37.   a.fi *= (lcm / a.se);
  38.   b.fi *= (lcm / b.se);
  39.   a.se = b.se = lcm;
  40.   a.fi += b.fi;
  41.   return a;
  42. }
  43.  
  44. ii min(ii a, ii b) {
  45.   return a.fi * b.se < b.fi * a.se ? a : b;
  46. }
  47.  
  48. int main() {
  49.   cin.tie(0)->sync_with_stdio(0);
  50.   cin >> n >> m >> k;
  51.   gr.assign(n, vector<int>());
  52.  
  53.   for (int i = 0; i < k; ++i) {
  54.     int x; cin >> x, --x;
  55.     wormholes.push_back(x);
  56.   }
  57.  
  58.   for (int i = 0; i < m; ++i) {
  59.     int a, b; cin >> a >> b, --a, --b;
  60.     gr[a].push_back(b);
  61.     gr[b].push_back(a);
  62.   }
  63.  
  64.   vector<int> dist[2];
  65.   dist[0].assign(n, INF);
  66.   dist[1].assign(n, INF);
  67.  
  68.   bfs(0, dist[0]);
  69.   bfs(n-1, dist[1]);
  70.  
  71.   i64 S = 0;
  72.   for (int s : wormholes) {
  73.     S += dist[1][s];
  74.   }
  75.  
  76.   ii ans = {dist[0][n-1], 1};
  77.  
  78.   for (int s : wormholes) {
  79.     ans = min(ans, sum({dist[0][s], 1}, {S - dist[1][s], k - 1}));
  80.   }
  81.  
  82.   ans = normalize(ans);
  83.   cout << ans.fi << '/' << ans.se << '\n';
  84.  
  85.   return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment