首页 > 代码库 > HDU 2586 How far away ？ (LCA，Tarjan， spfa)
HDU 2586 How far away ？ (LCA，Tarjan， spfa)
题意：给定N个节点一棵树，现在要求询问任意两点之间的简单路径的距离，其实也就是最短路径距离。
析：用LCA问题的Tarjan算法，利用并查集的优越性，产生把所有的点都储存下来，然后把所有的询问也储存下来，然后从树根开始搜索这棵树，
在搜索子树的时候，把并查集的父结点不断更新，在搜索时计算答案，d[i] 表示从根结点到 i 结点的距离，然后分别计算到两个结点的距离，
再减去2倍的根结点到他们公共最近的结点距离，就OK了。不过这个题有个坑人的地方，不用输出那个空行，否则就是PE。
因为这个题询问比较少，所以我们可以用spfa来做。
代码如下：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <cstdio>#include <string>#include <cstdlib>#include <cmath>#include <iostream>#include <cstring>#include <set>#include <queue>#include <algorithm>#include <vector>#include <map>#include <cctype>#include <cmath>#include <stack>#define freopenr freopen("in.txt", "r", stdin)#define freopenw freopen("out.txt", "w", stdout)using namespace std; typedef long long LL;typedef pair<int, int> P;const int INF = 0x3f3f3f3f;const double inf = 0x3f3f3f3f3f3f;const double PI = acos(-1.0);const double eps = 1e-8;const int maxn = 4e4 + 5;const int mod = 1e9 + 7;const int dr[] = {-1, 0, 1, 0};const int dc[] = {0, 1, 0, -1};const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};int n, m;const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};inline int Min(int a, int b){ return a < b ? a : b; }inline int Max(int a, int b){ return a > b ? a : b; }inline LL Min(LL a, LL b){ return a < b ? a : b; }inline LL Max(LL a, LL b){ return a > b ? a : b; }inline bool is_in(int r, int c){ return r >= 0 && r < n && c >= 0 && c < m;}struct Edge{ int to, w, next;};struct node{ int to, id, next;};Edge a[maxn<<1];node b[405];int p[maxn], head[maxn<<1], cnt, cnt1, head1[maxn];int rec[205][3], d[maxn];bool vis[maxn]; int Find(int x){ return x == p[x] ? x : p[x] = Find(p[x]); } void add(int u, int v, int w){ a[cnt].to = v; a[cnt].w = w; a[cnt].next = head[u]; head[u] = cnt++;} void add1(int u, int v, int id){ b[cnt1].to = v; b[cnt1].id = id; b[cnt1].next = head1[u]; head1[u] = cnt1++;} void Tarjan(int u){ vis[u] = true; for(int i = head1[u]; ~i; i = b[i].next){ int v = b[i].to; if(vis[v]) rec[b[i].id][2] = Find(v); } for(int i = head[u]; ~i; i = a[i].next){ int v = a[i].to; if(!vis[v]){ d[v] = d[u] + a[i].w; Tarjan(v); p[v] = u; } }} int main(){ int T; cin >> T; while(T--){ scanf("%d %d", &n, &m); for(int i = 0; i <= n; ++i) p[i] = i; int u, v, w; cnt = cnt1 = 0; memset(head, -1, sizeof head); memset(head1, -1, sizeof head1); for(int i = 1; i < n; ++i){ scanf("%d %d %d", &u, &v, &w); add(u, v, w); add(v, u, w); } for(int i = 0; i < m; ++i){ scanf("%d %d", &u, &v); add1(u, v, i); add1(v, u, i); rec[i][0] = u; rec[i][1] = v; } memset(vis, false, sizeof vis); d[1] = 0; Tarjan(1); for(int i = 0; i < m; ++i) printf("%d\n", d[rec[i][0]] + d[rec[i][1]] - 2*d[rec[i][2]]); //printf("\n"); } return 0;}
第二种写法：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <cstdio>#include <string>#include <cstdlib>#include <cmath>#include <iostream>#include <cstring>#include <set>#include <queue>#include <algorithm>#include <vector>#include <map>#include <cctype>#include <cmath>#include <stack>#define freopenr freopen("in.txt", "r", stdin)#define freopenw freopen("out.txt", "w", stdout)using namespace std;typedef long long LL;typedef pair<int, int> P;const int INF = 0x3f3f3f3f;const double inf = 0x3f3f3f3f3f3f;const double PI = acos(-1.0);const double eps = 1e-8;const int maxn = 4e4 + 5;const int mod = 1e9 + 7;const int dr[] = {-1, 0, 1, 0};const int dc[] = {0, 1, 0, -1};const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};int n, m;const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};inline int Min(int a, int b){ return a < b ? a : b; }inline int Max(int a, int b){ return a > b ? a : b; }inline LL Min(LL a, LL b){ return a < b ? a : b; }inline LL Max(LL a, LL b){ return a > b ? a : b; }inline bool is_in(int r, int c){ return r >= 0 && r < n && c >= 0 && c < m;}vector<int> G[maxn], w[maxn], q[maxn], id[maxn];int d[maxn], p[maxn], ans[205];bool vis[maxn];int Find(int x){ return x == p[x] ? x : p[x] = Find(p[x]); }void Tarjan(int u){ vis[u] = true; for(int i = 0; i < G[u].size(); ++i){ int v = G[u][i]; if(!vis[v]){ d[v] = d[u] + w[u][i]; Tarjan(v); p[v] = u; } } for(int i = 0; i < q[u].size(); ++i){ int v = q[u][i]; if(vis[v]) ans[id[u][i]] = d[u] + d[v] - 2*d[Find(v)]; }}int main(){ int T;; cin >> T; while(T--){ scanf("%d %d", &n, &m); for(int i = 1; i <= n; ++i) G[i].clear(), w[i].clear(), q[i].clear(), id[i].clear(), p[i] = i; int u, v, val; for(int i = 1; i < n; ++i){ scanf("%d %d %d", &u, &v, &val); G[u].push_back(v); G[v].push_back(u); w[u].push_back(val); w[v].push_back(val); } for(int i = 0; i < m; ++i){ scanf("%d %d", &u, &v); q[u].push_back(v); q[v].push_back(u); id[u].push_back(i); id[v].push_back(i); } memset(vis, false, sizeof vis); d[1] = 0; Tarjan(1); for(int i = 0; i < m; ++i) printf("%d\n", ans[i]); } return 0;}
spfa:
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <cstdio>#include <string>#include <cstdlib>#include <cmath>#include <iostream>#include <cstring>#include <set>#include <queue>#include <algorithm>#include <vector>#include <map>#include <cctype>#include <cmath>#include <stack>#define freopenr freopen("in.txt", "r", stdin)#define freopenw freopen("out.txt", "w", stdout)using namespace std;typedef long long LL;typedef pair<int, int> P;const int INF = 0x3f3f3f3f;const double inf = 0x3f3f3f3f3f3f;const double PI = acos(-1.0);const double eps = 1e-8;const int maxn = 4e4 + 5;const int mod = 1e9 + 7;const int dr[] = {-1, 0, 1, 0};const int dc[] = {0, 1, 0, -1};const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};int n, m;const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};inline int Min(int a, int b){ return a < b ? a : b; }inline int Max(int a, int b){ return a > b ? a : b; }inline LL Min(LL a, LL b){ return a < b ? a : b; }inline LL Max(LL a, LL b){ return a > b ? a : b; }inline bool is_in(int r, int c){ return r >= 0 && r < n && c >= 0 && c < m;}struct node{ int to, w, next;};node a[maxn<<1];int cnt;int head[maxn];bool vis[maxn];int d[maxn];int q[maxn];void add(int u, int v, int w){ a[cnt].to = v; a[cnt].w = w; a[cnt].next = head[u]; head[u] = cnt++;}int spfa(int s, int t){ memset(vis, false, sizeof vis); fill(d, d+n+1, INF); int front = 0, rear = 0; q[rear++] = s; d[s] = 0; while(front < rear){ int u = q[front++]; vis[u] = false; for(int i = head[u]; ~i; i = a[i].next){ int v = a[i].to; if(d[v] > d[u] + a[i].w){ d[v] = d[u] + a[i].w; if(!vis[v]) q[rear++] = v, vis[v] = true; } } } return d[t];}int main(){ int T; cin >> T; while(T--){ scanf("%d %d", &n, &m); int u, v, w; cnt = 0; memset(head, -1, sizeof head); for(int i = 1; i < n; ++i){ scanf("%d %d %d", &u, &v, &w); add(u, v, w); add(v, u, w); } while(m--){ scanf("%d %d", &u, &v); printf("%d\n", spfa(u, v)); } } return 0;}
HDU 2586 How far away ？ (LCA，Tarjan， spfa)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。