洛谷P2912 [USACO08OCT]Pasture Walking G 题解

题目链接：P2912 [USACO08OCT]Pasture Walking G

题意：有 $N(2\le N\le1000)$ 头奶牛，编号为 $1$ 到 $W$ ，它们正在同样编号为 $1$ 到 $N$ 的牧场上行走.为了方便，我们假设编号为 $i$ 的牛恰好在第 $i$ 号牧场上.

有一些牧场间每两个牧场用一条双向道路相连，道路总共有 $N - 1$ 条，奶牛可以在这些道路 上行走.第 $i$ 条道路把第 $A_i$ 个牧场和第 $B_i$ 个牧场连了起来 $(1 \le A_i \le N; 1 \le B_i \le N)$ ，而它的长度 是 $1 \le L_i \le 10,000$.在任意两个牧场间，有且仅有一条由若干道路组成的路径相连.也就是说，所有的道路构成了一棵树.

奶牛们十分希望经常互相见面.它们十分着急，所以希望你帮助它们计划它们的行程，你只 需要计算出 $Q(1 < Q < 1000)$ 对点之间的路径长度•每对点以一个询问 $p_1,p_2 (1 \le p_1 \le N; 1 \le p_2 \le N)$ 的形式给出.

按照解题的思路，首先想到的是Floyd

你看它多简单多好用

然而它的时间复杂度是 $O(n^3)$

我们来观察一下Floyd

for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

由于给定的是一棵树（且无向边），那么

$\forall u \in V$ 有且仅有 $2$ 个的 $v_1,v_2 \in V$ 使得 $(u,v_1) , (u,v_2) \in E$

且 $v_1,v_2$ 只可能是 $u$ 的父亲或儿子

说人话就是每个结点最多连出去两个结点

那么很多时候f[i][k]都是无效的枚举（都是INF啊）

于是我们可以剪枝

for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
        if(f[i][k]!=INF)
            for(int j=1; j<=n; j++)
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

于是时间复杂度就降到了 $O(n^2)$

代码如下 （好丑啊qwq）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gc() getchar()
#define pc(a) putchar(a)
#define INF 0x3f3f3f3f
#define MAXN (int)(1e3+5)
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){k=-k;pc('-');}
    if(k>9)write(k/10);
    pc(k%10+'0');
}
int n,Q,f[1005][1005];
signed main()
{
    read(n);read(Q);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            f[i][j]=INF;
    for(int i=1,u,v,w; i<n; i++)
    {
        read(u);read(v);read(w);
        f[u][v]=f[v][u]=w;
    }
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            if(f[i][k]!=INF)
                for(int j=1; j<=n; j++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    while(Q--)
    {
        int x,y;read(x);read(y);
        write(f[x][y]);pc('\n');
    }
    return 0;
}