DreamAngel
如果你希望成功，以恒心為良友，以經驗為參謀，以小心為兄弟，以希望為哨兵。

隨筆 - 147 文章 - 71 trackbacks - 0

<

2025年7月

>

日

一

二

三

四

五

六

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

我的其它Blog：
www.cppblog.com/dreamangel/
blog.csdn.net/fjnu_angel/

常用鏈接

留言簿(1)

隨筆分類(146)

隨筆檔案(147)

文章分類(28)

文章檔案(28)

喜歡的Blog

搜索

閱讀排行榜

評論排行榜

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 飛翔天使閱讀(1079) 評論(0) 編輯收藏所屬分類: poj

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB 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）

常用鏈接

留言簿(1)

隨筆分類(146)

隨筆檔案(147)

文章分類(28)

文章檔案(28)

喜歡的Blog

搜索

最新評論

閱讀排行榜

評論排行榜