Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const long long N = 1e5 + 7, inf = 1e17;
- struct e {
- long long c;
- int v;
- };
- vector <e> g[N], q, Q;
- int n, m, s = -1, f = -1, u[N], w, U[N];
- vector <long long> d(N, inf), D(N, inf), a(N, 0);
- void dfs(int v, int x) {
- if (g[v].size() != 2) {
- if (s == -1)
- s = v;
- else
- if (f == -1)
- f = v;
- u[v] = -1;
- return;
- }
- u[v] = x;
- for (auto i : g[v])
- if (!u[i.v])
- dfs(i.v, x);
- }
- void F (int pv, int v, int e) {
- U[v] = 1;
- a[v] = a[pv] + e;
- for (auto i : g[v])
- if (!U[i.v])
- F(v, i.v, i.c);
- }
- main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- freopen("input.txt", "r", stdin);
- cin >> n >> m >> w;
- for (int i = 0; i < m; ++i) {
- int x, y, c;
- cin >> x >> y >> c;
- g[--x].push_back({c, --y});
- g[y].push_back({c, x});
- }
- for (int i = 0; i < n; ++i)
- if (!u[i])
- dfs(i, i + 1);
- U[s] = U[f] = 1;
- for (auto i : g[s])
- if (!U[i.v])
- F(s, i.v, i.c);
- d[s] = 0;
- q.push_back({0, s});
- D[f] = 0;
- Q.push_back({0, f});
- for (int i = 0; i < q.size(); ++i) {
- int u = q[i].v;
- for (auto j : g[u]) {
- int v = j.v;
- long long c = j.c;
- if (d[v] > c + d[u])
- d[v] = c + d[u],
- q.push_back({d[v], v});
- }
- }
- for (int i = 0; i < Q.size(); ++i) {
- int u = Q[i].v;
- for (auto j : g[u]) {
- int v = j.v;
- long long c = j.c;
- if (D[v] > c + D[u])
- D[v] = c + D[u],
- Q.push_back({D[v], v});
- }
- }
- for (int i = 0; i < w; ++i) {
- int x, y;
- cin >> x >> y;
- --x;
- --y;
- if (x == s && y == f || y == s && x == f) {
- cout << d[f] << ' ';
- continue;
- }
- cout << min(min({min(d[x], D[x]) + min(d[y], D[y]) + d[f], d[x] + d[y], D[x] + D[y]}), u[x] == u[y] ? abs(a[x] - a[y]) : inf) << ' ';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement