bzoj1641 / P2888 [USACO07NOV]牛栏Cow Hurdles

Floyd

$n<=300$？果断Floyd

给出核心式，自行体会

$d[i][j]=min(d[i][j],max(d[i][k],d[k][j]))$

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int max(int a,int b){return a>b?a:b;}
 6 int min(int a,int b){return a<b?a:b;} 
 7 int d[302][302],n,m,t;
 8 int main(){
 9     memset(d,127,sizeof(d));
10     scanf("%d%d%d",&n,&m,&t);
11     for(int i=1,q1,q2,q3;i<=m;++i){
12         scanf("%d%d%d",&q1,&q2,&q3);
13         d[q1][q2]=q3;
14     }
15     for(int k=1;k<=n;++k)
16         for(int i=1;i<=n;++i)
17             for(int j=1;j<=n;++j)
18                 d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
19     for(int i=1,q1,q2;i<=t;++i){
20         scanf("%d%d",&q1,&q2);
21         if(d[q1][q2]==d[0][0]) printf("-1
");
22         else printf("%d
",d[q1][q2]);
23     }return 0;
24 }

View Code