最短路变形或最大生成树变形。
问 目标两地之间能通过的小重量。
用最短路把初始赋为INF，其他为0.然后找 dis[v]=min(dis[u], d);
生成树就是把最大生成树找出来，直到出发和终点能沟通的时候，最小的边就是。
Kruskal：
#include #include #include #include #include #include #include #include #include #include #include #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; int n,m; int fa[201]; map city; struct lx { int u,v,len; }l[19901]; int father(int x) { if(x!=fa[x]) return fa[x]=father(fa[x]); } bool cmp(lx a, lx b) { return a.len>b.len; } int main() { int nn=1; while(scanf("%d%d",&n,&m),n||m) { for(int i=0;i<=n;i++) fa[i]=i; city.clear(); char a[31],b[31]; int len,u,v,cot=0; for(int i=0;i