Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- using namespace std;
- using i64 = long long;
- using ii = pair<i64, i64>;
- const int INF = 0x3f3f3f3f;
- int n, m, k;
- vector<int> wormholes;
- vector<vector<int>> gr;
- void bfs(int s, vector<int> &d) {
- queue<int> q;
- d[s] = 0;
- q.push(s);
- while (!q.empty()) {
- int u = q.front(); q.pop();
- for (int to : gr[u]) if (d[to] == INF) {
- d[to] = d[u] + 1;
- q.push(to);
- }
- }
- }
- ii normalize(ii a) {
- i64 g = __gcd(a.fi, a.se);
- a.fi /= g;
- a.se /= g;
- return a;
- }
- ii sum(ii a, ii b) {
- a = normalize(a);
- b = normalize(b);
- i64 lcm = a.se / __gcd(a.se, b.se) * b.se;
- a.fi *= (lcm / a.se);
- b.fi *= (lcm / b.se);
- a.se = b.se = lcm;
- a.fi += b.fi;
- return a;
- }
- ii min(ii a, ii b) {
- return a.fi * b.se < b.fi * a.se ? a : b;
- }
- int main() {
- cin.tie(0)->sync_with_stdio(0);
- cin >> n >> m >> k;
- gr.assign(n, vector<int>());
- for (int i = 0; i < k; ++i) {
- int x; cin >> x, --x;
- wormholes.push_back(x);
- }
- for (int i = 0; i < m; ++i) {
- int a, b; cin >> a >> b, --a, --b;
- gr[a].push_back(b);
- gr[b].push_back(a);
- }
- vector<int> dist[2];
- dist[0].assign(n, INF);
- dist[1].assign(n, INF);
- bfs(0, dist[0]);
- bfs(n-1, dist[1]);
- i64 S = 0;
- for (int s : wormholes) {
- S += dist[1][s];
- }
- ii ans = {dist[0][n-1], 1};
- for (int s : wormholes) {
- ans = min(ans, sum({dist[0][s], 1}, {S - dist[1][s], k - 1}));
- }
- ans = normalize(ans);
- cout << ans.fi << '/' << ans.se << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment