亚洲嫩草影院久久精品,国产A级毛片久久久精品毛片,久久久久人妻精品一区三寸蜜桃

pku 1135

2009年7月29日

題目鏈接：PKU 1135 Domino Effect

分類：（Dijkastra+枚舉）

題目分析與算法原型
         這道題目的意思大致是給你n個(gè)骨牌，以及某些骨牌之間的邊，這些邊的權(quán)值代表，從這條邊的某一端（某一骨牌）開(kāi)始倒，一直倒到該邊的終點(diǎn)（該邊的另一個(gè)骨牌）所需的時(shí)間，然后題目的求的是，從編號(hào)為1的骨牌開(kāi)始倒（注意，某一個(gè)骨牌倒的時(shí)候，連同與其相鄰的邊都同時(shí)開(kāi)始往外面倒），求最后倒的骨牌的位置（在某兩個(gè)骨牌之間或者是剛給你的n個(gè)骨牌的其中一個(gè)）并輸出時(shí)間..........
         其實(shí)，因?yàn)槊總€(gè)牌倒的同時(shí)都連帶與其連接的所有邊也同時(shí)倒，不難看出，當(dāng)從骨牌1一直倒到某個(gè)骨牌x的時(shí)候，其實(shí)從1到x間的路徑必定是最短路徑，因?yàn)榭隙ㄊ茄刂疃痰穆窂讲拍芟鹊竭_(dá)x么，考慮到這點(diǎn)，問(wèn)題就已經(jīng)解決一半了，我們可以先算出從1點(diǎn)出發(fā)的到其他所有點(diǎn)的最短路徑，然后取這些最短路徑中最長(zhǎng)的那個(gè)點(diǎn)y，然后再枚舉所有與這個(gè)點(diǎn)相鄰的點(diǎn)      （這里需要除去 path[y]這點(diǎn)），假設(shè)z是其中一個(gè)點(diǎn)，然后找能使得(dis[y]+dis[z]+map[y][z])/2最長(zhǎng)的那個(gè)點(diǎn),若(dis[y]+dis[z]+map[y][z])/2>dis[y],則說(shuō)明最后一個(gè)是y,若(dis[y]+dis[z]+map[y][z])/2=dis[y]則說(shuō)明,最后一個(gè)處與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為源點(diǎn)
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;//此語(yǔ)句對(duì)于非連通圖是必須的，表示當(dāng)前已經(jīng)不存在路徑了
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 閱讀(270) 評(píng)論(0) 編輯收藏引用

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

pku 1135

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜