求最短路的最大值。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/2 19:13:45
* File Name: poj1125.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-11);
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(107);
int n,ans,pos,g[kMaxn][kMaxn];
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d",&n)==1 && n)
{
memset(g,0x7f,sizeof(g));
for(int i=1;i<=n;i++)
{
int m;
scanf("%d",&m);
for(int j=1;j<=m;j++)
{
int a,t;
scanf("%d%d",&a,&t);
g[i][a]=t;
}
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(g[i][k]<kInf && g[k][j]<kInf && g[i][j]>g[i][k]+g[k][j])
g[i][j]=g[i][k]+g[k][j];
ans=kInf;
for(int i=1;i<=n;i++)
{
int t(0);
for(int j=1;j<=n;j++)
if(i!=j)
t=max(t,g[i][j]);
if(ans>t)
{
ans=t;
pos=i;
}
}
if(ans<kInf)
printf("%d %d\n",pos,ans);
else
printf("disjoint\n");
}
return 0;
}
posted on 2011-08-02 19:25
lee1r 閱讀(245)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論