本文共 2489 字，大约阅读时间需要 8 分钟。
http://acm.whu.edu.cn/land/problem/detail?problem_id=1542
题意说，有n个点和m条边，有的点之间是距离为0，距离为零的点可以构成一个联通块，还有的点之间距离大于0。联通块的个数不会超过200，问你任意两个点之间的最短距离。
解题思路：
首先既然是不超过200个联通块，要你求最短距离，直接可以用floyed撸O(n^3)；然后只要想到用并查集做缩点，并且记录每个点在哪个联通块里就可以了。
题目代码：
#include #include #include #define FOR(a,b,c) for (int a=b,_c=c;a<=_c;a++)#define REP(i,a) for(int i=0,_a=(a); i<_a; ++i)#define oo 1000000007using namespace std;typedef long long ll;typedef pair pii;const int maxn = 100100;struct Node{ int u, v, val;};Node edge[maxn];int p[maxn];int dis[222][222];int Map[maxn];int cnt;int find(int x){ return x != p[x] ? p[x]=find(p[x]) : x;}int main(){// freopen("data.in", "r", stdin); int m, n, q, fu, fv, f,ans; while(scanf("%d", &n) != EOF && n != 0) { scanf("%d", &m); FOR(i, 1, n) p[i] = i; REP(i, m) { scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].val); if(edge[i].val == 0) { fu = find(edge[i].u); fv = find(edge[i].v); if(fu != fv) p[fv] = fu; } } cnt = 0; FOR(i, 1, n) { f = find(i); if(f == i) { Map[i] = ++cnt; } } FOR(i, 1, n) { f = find(i); if(f != i) { Map[i] = Map[f]; } } FOR(i, 1, cnt){ FOR(j, 1, cnt) { dis[i][j] = oo; } dis[i][i] = 0; } REP(i, m) { if(edge[i].val) { fu = find(edge[i].u); fv = find(edge[i].v); fu = Map[fu]; fv = Map[fv]; dis[fu][fv] = min(dis[fu][fv], edge[i].val); dis[fv][fu] = min(dis[fv][fu], edge[i].val); } } FOR(k, 1, cnt) FOR(i, 1, cnt) FOR(j, 1, cnt) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); scanf("%d", &q); while(q--) { scanf("%d%d", &fu, &fv); fu = find(fu); fv = find(fv); if(fu == fv) { ans = 0; }else { fu = Map[fu]; fv = Map[fv]; ans = dis[fu][fv]; if(ans == oo) ans = -1; } printf("%d\n", ans); } } return 0;}
转载地址：http://mbhrb.baihongyu.com/