poj 3615 Cow Hurdles

继续复习

DP，图论

题意：有向图，n个点，m条边，t个查询。从点u到点v可能有多条路径，找出一条，使这条路径的权值最大的那条边的值在所有路径中是最小的，即最大值最小

状态转移方程：dp[i][j]表示从i到j的最小的最大值。

dp[i][j] = min{   dp[i][j]   ,   max(dp[i][k] , dp[k][j])   }

#include <cstdio>
#include <cstring>
#define N 310
#define INF 0x3f3f3f3f
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

int dp[N][N];

int main()
{
   int n,m,t;
   scanf("%d%d%d",&n,&m,&t);
   //while(scanf("%d%d%d",&n,&m,&t)!=EOF)
   //{
      memset(dp,0x3f,sizeof(dp));
      for(int i=0; i<m; i++)
      {
         int u,v,w;
         scanf("%d%d%d",&u,&v,&w);
         dp[u][v] = w;
      }

      for(int k=1; k<=n; k++)
         for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
            {
               int temp = max(dp[i][k] , dp[k][j]);
               dp[i][j] = min(dp[i][j] , temp);
            }

      for(int i=0; i<t; i++)
      {
         int u,v;
         scanf("%d%d",&u,&v);
         if(dp[u][v]  == INF)
            printf("-1\n");
         else
            printf("%d\n",dp[u][v]);
      }
   //}
   return 0;
}