欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P2888 [USACO07NOV]牛栏Cow Hurdles(Floyd算法)

程序员文章站 2022-06-03 18:28:26
...

P2888 [USACO07NOV]牛栏Cow Hurdles
P2888 [USACO07NOV]牛栏Cow Hurdles(Floyd算法)
行 1…T: 行 i 为一个整数,表示任务i路径上最高的栏的高度的最小值。如果无法到达,输出 -1。

5 6 3
1 2 12
3 2 8
1 3 5
2 5 3
3 4 4
2 4 8
3 4
1 2
5 1
4
8
-1

注意:memset(dis,0x7f,sizeof dis);dis[0][0]=0x7f7f7f7f
但是dis必须是int型的

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"#  "<<x<<" "<<endl;
typedef long long ll;
const ll mod=2147483647000;
const ll N=307;
const ll INF=0x7f;
int dis[N][N],n,m,t;
int main()
{
    ll a,b,c;
    cin>>n>>m>>t;
    memset(dis,INF,sizeof dis);
    for(int i=1;i<=m;++i)
        cin>>a>>b>>c,dis[a][b]=c;
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                dis[i][j]=min(dis[i][j],max(dis[i][k],dis[k][j]));
    int x,y;
    for(int i=1;i<=t;++i)
    {
        cin>>x>>y;
        if(dis[x][y]==0x7f7f7f7f)cout<<"-1"<<endl;
        else cout<<dis[x][y]<<endl;
    }
    return 0;
}

相关标签: 最短路