问题其实只要想到这个路径必然可以用最大生成树上的路径来替代 基本就可以解决了
为什么一定可以用最大生成树来替代呢
如果我们将问题变形思考：
把问题变为 求某个城市 I到任意城市 j 货车可以装载的最大重量 C[j] 当 I==j时 C[i]=INF(无穷重量)
我们将 C[j]被确定的城市 和还未被确定的城市看做两个集合
刚开始 只有C[I]是确定的 C[i]=INF
而C[j]未被确定的这些点 中的某些点 与点 i存在边

这些边 将图分割成两部分 如果想从 未发现点到达点 I 就必须选择 其中至少一条 不然 点i将被孤立
这是不可能的 如果点I 被孤立 那么他将不能到达任何点 则此时 C[j]=-1 (j!=I)
与实际情况相驳
所以 我们一定要选择一条边
直觉告诉我们 选择权值最大的边 会是较优的选择
但是不是最优的呢
我们使用归纳法证明 ：
首先 ：
刚开始 只有点I是被发现点
与之连接的所有点中 点k与它形成了一个边 权值是最大的之一
即 边 ： E[I][k]
由于别的边权小于等于 E[I][k]所以 别的路径的最大载重<=E[I][k];

其次 ：
由于被发现点是互相可达的 且已经是最优结果 我们将他们缩为一个点 并从新构图 这样 又可以归纳为上面问题 套用上面的 结论 依然是找未被发点与被发现点连接的边中的最大权边
上面的过程很明显 这样做 一定会得到棵树
而且 对prim算法 了解的人都会发现 上面的过程实质就是 prim算法过程 这也就是说 变形问题的所有路径 必然在最大生成树 或者数个最大生成树组成的森林
所以 由于i可以任意指定 所以 任何点对的最优路径一定可以用确定的一颗最大生产树上的简单路径替代
为了方便处理森林 我们加入超级根节点 0结点 并让他与别的树根形成的边为-1

由于是树 结构 所有 不存在环 且 简单路径是唯一的
这也就是说 路径中存在0结点的路径 其实 两点在实际情况是不可达的 这也是为什么 超级根节点连接的边 是-1权的原因
```c++
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#define abs(a) ((a)>0?(a):-(a))
#define INF 0x3f3f3f3f
#define MAXN 10001
using namespace std;
//*******************************
struct edge1
{
int to,w;
edge1(){to=w=0;}
edge1(int to,int w):to(to),w(w){}
};
struct edge2
{
int from,to,w;
edge2(){from=to=w=0;}
edge2(int from,int to,int w):from(from),to(to),w(w){}
bool operator < (const edge2&a)const
{
return w>a.w;
}
};
edge2 data[MAXN*5];
struct Bf //并查集
{
int A[MAXN];
Bf() { for(int i=0;i<MAXN;i++)A[i]=i; }
int find(int a)
{
if(A[a]==a)return a;
return A[a]=find(A[a]);
}
void mer(int a,int b)
{
int U1=find(a);
int U2=find(b);
A[U1]=U2;
}
}bf;

struct Tree//最小生成树
{
int n;
int m;
bool used[MAXN];
vector<edge1>A[MAXN];
void push(edge2 a)
{
A[a.from].push_back(edge1(a.to,a.w));
A[a.to].push_back(edge1(a.from,a.w));
}
void map(edge2 D[])//建图
{
sort(D,D+m);
for(int i=0;i<m;i++)
{
int U1=bf.find(D[i].from);
int U2=bf.find(D[i].to);
if(U1!=U2)
{
push(D[i]);
bf.mer(U1,U2);
}
}
for(int i=1;i<=n;i++)
if(!used[bf.find(i)])
{
push(edge2(0,i,-1));
used[bf.find(i)]=true;

}
memset(used,false,sizeof(used));//不影响下次使用
}
};

struct L//倍增计算 公共祖先+链上最小边权
{
Tree T;
int E_min[MAXN][31];
int fat[MAXN][31];
int pth[MAXN];
L()
{
memset(fat,0,sizeof(fat));
memset(pth,0,sizeof(pth));
memset(E_min,0x3f,sizeof(E_min));
}
void DFS(int root,int ph)
{
T.used[root]=true;
pth[root]=ph;
for(int i=0;i<T.A[root].size();i++)
{
edge1 &e=T.A[root][i];
if(!T.used[e.to])
{
DFS(e.to,ph+1);
fat[e.to][0]=root;
E_min[e.to][0]=e.w;
}
}
T.used[root]=false;
}
void init()
{
for(int j=1;j<31;j++)
for(int i=0;i<=T.n;i++)
fat[i][j]=fat[fat[i][j-1]][j-1];
for(int j=1;j<31;j++)
for(int i=0;i<=T.n;i++)
E_min[i][j]=min(E_min[i][j-1],E_min[fat[i][j-1]][j-1]);
}
int Qfind(int U,int V)
{
int a=INF;
if(pth[V]>pth[U])swap(U,V);
int dd=pth[U]-pth[V];//计算高度差
for(int i=0;i<30;i++)
if((1<<i)&dd)
{
a=min(E_min[U][i],a);
U=fat[U][i];
}
if(U==V)return a;
for(int i=30;i>-1;i--)
if(fat[U][i]!=fat[V][i])
{
a=min(min(E_min[U][i],E_min[V][i]),a);
U=fat[U][i];
V=fat[V][i];
}
return min(min(E_min[U][0],E_min[V][0]),a);
}
}LCA;
int main()
{
scanf("%d%d",&LCA.T.n,&LCA.T.m);
for(int i=0;i<LCA.T.m;i++)
scanf("%d%d%d",&data[i].from,&data[i].to,&data[i].w);
LCA.T.map(data);
LCA.DFS(0,0);
LCA.init();
int q,u,v;
scanf("%d",&q);
for(int i=0;i<q;i++)
{
scanf("%d%d",&u,&v);
printf("%d\n",LCA.Qfind(u,v));
}
return 0;
}
```

花5分钟想了个变形FLOYD，本来以为错的，还好 30 分
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::max;
using std::min;
int n,m,q;
int map[1010][1010];

int main(){
freopen("truck.in","r",stdin);
freopen("truck.out","w",stdout);
scanf("%d%d",&n,&m);
memset(map,-1,sizeof(map));
for(int i=1;i<=m;i++){
int u,v,val;
scanf("%d%d%d",&u,&v,&val);
if(val>map[u][v])
map[u][v]=map[v][u]=val;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
int t;
if(map[i][k]==-1||map[k][j]==-1)
continue;
t=min(map[i][k],map[k][j]);
if(map[i][j]==-1) map[i][j]=t;
else map[i][j]=max(t,map[i][j]);
}

scanf("%d",&q);
for(int i=1;i<=q;i++){
int p1,p2;
scanf("%d%d",&p1,&p2);
printf("%d\n",map[p1][p2]);
}
return 0;
}

UVA上的原题，怕是有人比赛前就做过。。。
```c++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int INF = 1000000000;
const int maxn = 10000 + 10;
const int maxm = 50000 + 10;
const int maxlog = 17;

struct Edge {
int u, v, w;
Edge (int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
bool operator < (const Edge &rhs) const {
return w > rhs.w;
}
};

int n, m, q;
int f[maxn];
int L[maxn], fa[maxn], cost[maxn];
int anc[maxn][maxlog], mincost[maxn][maxlog];
vector<int> G[maxn];
vector<Edge> tree;
vector<Edge> edges;

int findset (int x) { return f[x] == x ? x : f[x] = findset(f[x]);}

void AddEdge (int u, int v, int w) {
G[u].push_back(edges.size());
edges.push_back(Edge(u, v, w));
G[v].push_back(edges.size());
edges.push_back(Edge(v, u, w));
}

void dfs (int u, int f) {
fa[u] = f;
for (int i = 0; i < G[u].size(); i++) {
Edge &e = edges[G[u][i]];
if (e.v == f) continue;
L[e.v] = L[u]+1; cost[e.v] = e.w;
dfs(e.v, u);
}
}

void preprocess () {
for (int i = 0; i < n; i++) {
anc[i][0] = fa[i]; mincost[i][0] = cost[i];
for (int j = 1; (1<<j) < n; j++) anc[i][j] = -1;
}
for (int j = 1; (1<<j) < n; j++)
for (int i = 0; i < n; i++)
if (anc[i][j-1] >= 0) {
int a = anc[i][j-1];
anc[i][j] = anc[a][j-1];
mincost[i][j] = min(mincost[i][j-1], mincost[a][j-1]);
}
}

int query (int u, int v) {
int log;
if (L[u] < L[v]) swap(u, v);
for (log = 1; (1<<(log+1)) <= L[u]; log++);

int ans = INF;
for (int i = log; i >= 0; i--)
if (L[u]-(1<<i) >= L[v]) { ans = min(ans, mincost[u][i]); u = anc[u][i];}

if (u == v) return ans;

for (int i = log; i >= 0; i--)
if (anc[u][i] >= 0 && anc[u][i] != anc[v][i]) {
ans = min(ans, mincost[u][i]); u = anc[u][i];
ans = min(ans, mincost[v][i]); v = anc[v][i];
}

ans = min(ans, cost[u]);
ans = min(ans, cost[v]);
return ans;
}

int main ()
{
// freopen("in.txt", "r", stdin);
cin >> n >> m;
tree.reserve(m);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w; u--; v--;
tree.push_back(Edge(u, v, w));
}
sort(tree.begin(), tree.end());

for (int i = 0; i < n; i++) f[i] = i;
for (int i = 0; i < tree.size(); i++) {
int x = findset(tree[i].u), y = findset(tree[i].v);
if (x != y) {
f[x] = y;
AddEdge(tree[i].u, tree[i].v, tree[i].w);
}
}

for (int i = 0; i < n; i++)
if (L[i] == 0) dfs(i, -1);

preprocess();

cin >> q;
while(q--) {
int u, v;
cin >> u >> v; u--; v--;
if (findset(u) != findset(v)) cout << "-1\n";
else cout << query(u, v) << "\n";
}
return 0;
}
```

为什么这题这么简单，也许是我太聪明了，恍恍惚惚恍恍惚惚恍恍惚惚恍恍惚惚黑乎乎

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x7f7f7f7f;
const int MAXN = 10000 + 5;
struct ms{int u,v,w;}mst[MAXN*5];
bool cmp(const ms&x,const ms&y){return x.w>y.w;}
int ufs[MAXN];
int find(int x)
{
int t=x,tt;
while(t!=ufs[t])t=ufs[t];
while(x!=ufs[x])
{
tt=ufs[x];
ufs[x]=t;
x=tt;
}
return t;
}
int e=0;
int fst[MAXN],from[MAXN<<1],to[MAXN<<1],len[MAXN<<1],next[MAXN<<1];
inline void add(int f,int t,int w)
{
from[e]=f;
to[e]=t;
len[e]=w;
next[e]=fst[f];
fst[f]=e++;
}
void pr(int i){printf("%d%d%d",from[i],to[i],len[i]);}
int fa[MAXN][30],w[MAXN][30],dep[MAXN];
void dfs(int x,int la,int wt,int d)
{
//printf("x=%d la=%d wt=%d d=%d\n",x,la,wt,d);
fa[x][0]=la;w[x][0]=wt;dep[x]=d;
for(int i=fst[x];i;i=next[i])if(to[i]!=la)dfs(to[i],x,len[i],d+1);
}
int k,pow[30];
int lca(int u,int v)
{
int ans = INF;
if(dep[u]>dep[v])swap(u,v);
for(int i=k;i>=0;i--)
{
if(pow[i]<=dep[v]-dep[u])
{
ans=min(ans,w[v][i]);
v=fa[v][i];
}
}
for(int i=k;i>=0;i--)
{
if(fa[v][i]!=fa[u][i])
{
ans=min(ans,min(w[u][i],w[v][i]));
u=fa[u][i];
v=fa[v][i];
}
}
if(u!=v)ans=min(ans,min(w[u][0],w[v][0]));
return ans;
}
int main()
{

memset(fa,0,sizeof(fa));
int n,m;
scanf("%d%d",&n,&m);
for(k=0,pow[0]=1;pow[k]<=n;k++)pow[k+1]=pow[k]<<1;
for(int i=1;i<=n;i++)ufs[i]=i;
for(int i=1;i<=m;i++)scanf("%d%d%d",&mst[i].u,&mst[i].v,&mst[i].w);
sort(mst+1,mst+1+m,cmp);
for(int i=1;i<=m;i++)
{

int u=find(mst[i].u),v=find(mst[i].v);
if(u!=v)
{
ufs[v]=u;
add(u,v,mst[i].w);
add(v,u,mst[i].w);
}
}
for(int i=1;i<=n;i++)if(!fa[i][0])dfs(i,0,INF,1);
for(int j=1;j<=k;j++)
{
for(int i=1;i<=n;i++)
{
fa[i][j]=fa[fa[i][j-1]][j-1];
w[i][j]=min(w[i][j-1],w[fa[i][j-1]][j-1]);
}
}
int q;
scanf("%d",&q);
while(q--)
{
int u,v;
scanf("%d%d",&u,&v);
if (find(u)!=find(v))printf("-1\n");
else printf("%d\n",lca(u,v));
}
return 0;
}

吃屎啊，暴力就能过，搞毛？

跪求pascal！！！！！！！！！！！

咋成了C语言的天下了呢？？求Pascal的!!!!