poj1125（Stockbroker Grapevine）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1125
【题意简述】有向图(互相之间可能不等)中各顶点之间的最短路径问题。一个人收到消息后便开始向所有他能发送的人（因人以固定的不等时间（长度1~10））发送消息，当所有人都收到消息后的时间长短为评价标准。
【分析】Floyd算法。POJ这题的测试数据不严密，没有写disjoint也可以AC。

import java.util.*;

import java.io.*;

public class poj_1125{

public static void main(String rgs[]) throws Exception

{

Scanner cin = new Scanner(new BufferedInputStream(System.in));

int i,j,k,t=0,e,s,n = cin.nextInt();

while(n!=0){

int[][] a=new int[n+1][n+1];

for(i=1;i<=n;i++)

Arrays.fill(a[i],0xfffff);

for(i=1;i<=n;i++){

t = cin.nextInt();

for(j=1;j<=t;j++){

e = cin.nextInt();

s = cin.nextInt();

a[i][e]=s;

}

for(k=1;k<=n;k++){

for(i=1;i<=n;i++){

for(j=1;j<=n;j++){

if(a[i][k]+a[k][j]<a[i][j])

a[i][j]=a[i][k]+a[k][j];

}

int min=0xfffff,max;

k=0;

for(i=1;i<=n;i++){

max=0;

for(j=1;j<=n;j++){

if(i!=j && a[i][j]>max)

max=a[i][j];

}

if(max<min){

min=max;

k=i;

}

if(k>0)

System.out.println(k+" "+min);

else

System.out.println("disjoint");

n = cin.nextInt();

}

posted on 2009-09-18 10:16 飞翔天使阅读(1068) 评论(0) 编辑收藏所属分类: poj

常用链接

留言簿(1)

随笔分类(146)

随笔档案(147)

文章分类(28)

文章档案(28)

喜欢的Blog

搜索

最新评论

阅读排行榜

评论排行榜


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻知识库 C++博客博问管理
相关文章: poj1157（LITTLE SHOP OF FLOWERS） poj1396（Simple Arithmetics） poj ACM题型分类 poj1125（Stockbroker Grapevine） poj1835（宇航员） poj1163（The Triangle） poj1118（Lining Up） poj1129（Channel Allocation） poj1016（Numbers That Count） poj1001（Exponentiation）