给你一个有
个点和
条边的仙人掌图,和
组询问
每次询问两个点
,求两点之间的最短路。
第一行三个正整数
,意义如题目描述。
接下来
行,每行三个正整数
,表示
之间有一条权值为
的无向边。
然后
行,每行两个正整数
,询问
到
的最短路。
行,每行一个正整数,对应一次询问的结果。
9 10 2 1 2 1 1 4 1 3 4 1 2 3 1 3 7 1 7 8 2 7 9 2 1 5 3 1 6 4 5 6 1 1 9 5 7
5 6
9 10 3 1 2 1 2 3 1 2 4 4 3 4 2 4 5 1 5 6 1 6 7 2 7 8 2 8 9 4 5 9 2 1 9 5 8 3 4
7 5 2
样例1解释:
样例1中的仙人掌是这个样子的:
询问有两个,分别是询问
和
的最短路
显然答案分别为
和
。
数据范围:
建出圆方树, 然后搞搞倍增, 最后如果LCA下的两个点在一个方点中讨论一下走哪边就好了。
代码如下:
#include <cstdio> #include <cstring> #include <cmath> #include <cctype> #include <cstdlib> #include <algorithm> #define R register #define IN inline #define W while #define gc getchar() #define MX 20050 #define ll long long template <class T> IN void in(T &x) { x = 0; R char c = gc; for (; !isdigit(c); c = gc); for (; isdigit(c); c = gc) x = (x << 1) + (x << 3) + c - 48; } template <class T> IN T max(T a, T b) {return a > b ? a : b;} template <class T> IN T min(T a, T b) {return a < b ? a : b;} template <class T> IN T abs(T a) {return a > 0 ? a : -a;} int n, m, col, cnt, dcnt, q; int head[MX], h[MX], bel[MX], dfn[MX], low[MX], fat[MX][16], dep[MX]; ll tot[MX], dis[MX], Dis[MX][16]; struct Edge {int to, len, nex;} edge[MX * 4]; IN void add(R int from, R int to, R int len) {edge[++cnt] = {to, len, head[from]}, head[from] = cnt;} IN void add(R int from, R int to) {edge[++cnt] = {to, 0, h[from]}, h[from] = cnt;} IN void Getcir(R int rt, R int id) { R int now = edge[id].to; ++col; tot[col] = dis[now] - dis[rt] + edge[id].len; W (now ^ rt) { bel[now] = col; add(rt, now); Dis[now][0] = min(tot[col] - (dis[now] - dis[rt]), dis[now] - dis[rt]); now = fat[now][0]; } } void tarjan(R int now) { dfn[now] = low[now] = ++dcnt; for (R int i = head[now]; i; i = edge[i].nex) { if (edge[i].to == fat[now][0]) continue; if (!dfn[edge[i].to]) { fat[edge[i].to][0] = now; dis[edge[i].to] = dis[now] + edge[i].len; tarjan(edge[i].to); low[now] = min(low[now], low[edge[i].to]); } else low[now] = min(low[now], dfn[edge[i].to]); if (dfn[now] < low[edge[i].to]) add(now, edge[i].to), Dis[edge[i].to][0] = edge[i].len;//tree edges } for (R int i = head[now]; i; i = edge[i].nex) if (fat[edge[i].to][0] != now && dfn[now] < dfn[edge[i].to]) Getcir(now, i); } void pre(R int now) { for (R int i = 1; i <= 15; ++i) { fat[now][i] = fat[fat[now][i - 1]][i - 1]; if (!fat[now][i]) break; Dis[now][i] = Dis[now][i - 1] + Dis[fat[now][i - 1]][i - 1]; } for (R int i = h[now]; i; i = edge[i].nex) { if (edge[i].to == fat[now][0]) continue; fat[edge[i].to][0] = now; dep[edge[i].to] = dep[now] + 1; pre(edge[i].to); } } IN ll query(R int x, R int y) { ll ret = 0; if (dep[x] < dep[y]) std::swap(x, y); int del = dep[x] - dep[y]; for (R int i = 15; ~i; --i) { if ((del >> i) & 1) ret += Dis[x][i], x = fat[x][i]; } if (x == y) return ret; for (R int i = 15; ~i; --i) { if (fat[x][i] ^ fat[y][i]) { ret += Dis[x][i] + Dis[y][i]; x = fat[x][i], y = fat[y][i]; } } if (bel[x] && bel[x] == bel[y]) ret += min(abs(dis[x] - dis[y]), tot[bel[x]] - abs(dis[x] - dis[y])); else ret += Dis[x][0] + Dis[y][0]; return ret; } int main(void) { int foo, bar, l; in(n), in(m), in(q); for (R int i = 1; i <= m; ++i) { in(foo), in(bar), in(l); add(foo, bar, l), add(bar, foo, l); } tarjan(1); pre(1); W (q--) { in(foo), in(bar); printf("%lld\n", query(foo, bar)); } }