#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <cmath> using namespace std; const int MAXN = 40004; typedef pair<int, int> PAIR; vector<PAIR> edge[MAXN], query[MAXN]; int fa[MAXN], dis[MAXN], ans[MAXN]; bool vis[MAXN]; int n, m; int father(int x) { if (x == fa[x]) return x; return fa[x] = father(fa[x]); } void Init() { scanf("%d %d", &n, &m); int a, b, c; char d; for (int i=0; i<m; i++) { scanf("%d %d %d %c", &a, &b, &c, &d); edge[a].push_back(PAIR(b, c)); edge[b].push_back(PAIR(a, c)); } scanf("%d", &m); for (int i=0; i<m; i++) { scanf("%d %d", &a, &b); query[a].push_back(PAIR(b, i)); query[b].push_back(PAIR(a, i)); } memset(vis, false, sizeof(vis)); } void dfs(int u, int d) { fa[u] = u, dis[u] = d; vis[u] = true; for (size_t i=0; i<edge[u].size(); i++) { int v = edge[u][i].first, w = edge[u][i].second; if (!vis[v]) { dfs(v, d+w); fa[v] = u; } } for (size_t i=0; i<query[u].size(); i++) { int v = query[u][i].first, w = query[u][i].second; if (vis[v]) ans[w] = dis[u] + dis[v] - 2*dis[father(v)]; } } int main() { Init(); dfs(1, 0); for (int i=0; i<m; i++) printf("%d\n", ans[i]); return 0; } |
Double click to view unformatted code.