洛谷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;
}