久久精品国产久精国产爱,国产精品午夜在线观看,亚洲综合好骚

pku 1135

2009年7月29日

題目鏈接：PKU 1135 Domino Effect

分類：（Dijkastra+枚舉）

題目分析與算法原型
         這道題目的意思大致是給你n個骨牌，以及某些骨牌之間的邊，這些邊的權值代表，從這條邊的某一端（某一骨牌）開始倒，一直倒到該邊的終點（該邊的另一個骨牌）所需的時間，然后題目的求的是，從編號為1的骨牌開始倒（注意，某一個骨牌倒的時候，連同與其相鄰的邊都同時開始往外面倒），求最后倒的骨牌的位置（在某兩個骨牌之間或者是剛給你的n個骨牌的其中一個）并輸出時間..........
         其實，因為每個牌倒的同時都連帶與其連接的所有邊也同時倒，不難看出，當從骨牌1一直倒到某個骨牌x的時候，其實從1到x間的路徑必定是最短路徑，因為肯定是沿著最短的路徑才能先到達x么，考慮到這點，問題就已經解決一半了，我們可以先算出從1點出發的到其他所有點的最短路徑，然后取這些最短路徑中最長的那個點y，然后再枚舉所有與這個點相鄰的點      （這里需要除去 path[y]這點），假設z是其中一個點，然后找能使得(dis[y]+dis[z]+map[y][z])/2最長的那個點,若(dis[y]+dis[z]+map[y][z])/2>dis[y],則說明最后一個是y,若(dis[y]+dis[z]+map[y][z])/2=dis[y]則說明,最后一個處與y和z之間.........

Code:

1

#include<stdio.h>
2

#define max 1000000000
3

#define len 505
4

int n,m,a,b,l,map[len][len],dis[len],visit[len],path[len];
6

void init()
8

{
9

int i,j;
10

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

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

{
13

if(i==j)map[i][j]=0;
14

else map[i][j]=max;
15

}
16

}
17

void Dijkastra(int s)//s為源點
18

{
19

int i,j;
20

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

{
22

dis[i]=map[s][i];
23

visit[i]=0;
24

if(i!=s&&dis[i]<max)path[i]=s;
25

else path[i]=-1;
26

}
28

visit[s]=1;
29

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

{
31

int min=max,u;
32

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

if(visit[j]==0&&dis[j]<min)
34

{
35

u=j;
36

min=dis[j];
37

}
38

if(min==max)return;//此語句對于非連通圖是必須的，表示當前已經不存在路徑了
40

visit[u]=1;
42

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

if(visit[j]==0&&map[u][j]<max&&dis[u]+map[u][j]<dis[j])
44

{
45

dis[j]=dis[u]+map[u][j];
46

path[j]=u;
47

}
48

}
49

}
50

int main()
51

{
52

int i,ccase=1;;
53

while(scanf("%d%d",&n,&m)!=EOF)
54

{
55

if(n==0&&m==0)break;
56

init();
57

for(i=0;i<m;i++)
58

{
59

scanf("%d%d%d",&a,&b,&l);
60

if(l<map[a][b])
61

{
62

map[a][b]=l;
63

map[b][a]=l;
64

}
65

}
66

Dijkastra(1);
67

int _max=-1,num;
68

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

{
70

if(dis[i]>_max)
71

{
72

_max=dis[i];
73

num=i;
74

}
75

}
76

_max=-1;
77

int pos;
78

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

{
80

if(i!=path[num]&&map[num][i]<max)
81

{
82

if(dis[num]+dis[i]+map[num][i]>_max)
83

{
84

_max=dis[num]+dis[i]+map[num][i];
85

pos=i;
86

}
87

}
88

}
89

printf("System #%d\n",ccase++);
90

if(dis[pos]+map[num][pos]==dis[num])
91

printf("The last domino falls after %.1f seconds, at key domino %d.\n",(double)dis[num],num);
92

else
93

{
94

double res=(double)(dis[pos]+map[num][pos]+dis[num])/2;
95

if(num<pos)
96

printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n",res,num,pos);
97

else
98

printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n",res,pos,num);
99

100

}
101

printf("\n");
102

103

}
104

return 0;
105

}
106

posted on 2009-07-29 10:14 蝸牛也Coding 閱讀(279) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

pku 1135

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜