亚洲欧美另类在线,国产精品一区二区视频,欧美日韩综合视频网址

對于蝸牛來說，狂奔雖不代表極速，但展現的卻是一種拼盡全力的姿態........

pku 2253

2009年7月29日星期三

題目鏈接：PKU 2253 Frogger

分類：Dijkastra變種

題目分析與算法原型
其實這題和PKU 1797很像，Dijkastra中將判斷語句改成dis[j]=Mini(dis[j],Max(dis[u],map[u][j]))就行了，剛好和1797相反.........（PS：做了N多的最短路徑問題，從明天開始要換口味了，繼續學習圖論的其他經典算法）

Code:

1

#include<stdio.h>
2

#include<math.h>
3

#define len 205
4

#define max 1000000000
5

6

double pos[len][2],dis[len];
7

int visit[len],n;
8

9

double cal(int a,int b)
10

{
11

double res;
12

res=sqrt((pos[a][0]-pos[b][0])*(pos[a][0]-pos[b][0])+(pos[a][1]-pos[b][1])*(pos[a][1]-pos[b][1]));
13

return res;
14

}
15

double Max(double a,double b)
16

{
17

return a > b ? a : b;
18

}
19

void Dijkastra(int s, int v)//s為源點，v為終點（若有的話）
20

{
21

int i,j;
22

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

{
24

dis[i]=cal(s,i);
25

visit[i]=0;
26

}
27

visit[s]=1;
28

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

{
30

double min=max;
31

int 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

39

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

if(u==v)return ;//若題目是求從給定某個點到另一個給定的點之間的最短路徑時，加上這句節時
41

visit[u]=1;
42

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

if(visit[j]==0)
44

{
45

double k=cal(u,j);
46

if(Max(dis[u],k)<dis[j])
47

dis[j]=Max(dis[u],k);
48

}
49

}
50

}
51

int main()
52

{
53

int i,ccase=1;;
54

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

{
56

for(i=1;i<=n;i++)scanf("%lf%lf",&pos[i][0],&pos[i][1]);
57

Dijkastra(1,2);
58

printf("Scenario #%d\n",ccase++);
59

printf("Frog Distance = %.3lf\n\n",dis[2]);
60

61

}
62

return 1;
63

}
64

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

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




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

<

2015年9月

>

日

一

二

三

四

五

六

30

31

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

1

2

3

4

5

6

7

8

9

10

統計

隨筆 - 78
文章 - 0
評論 - 96
引用 - 0

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

積分 - 95328
排名 - 261

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

pku 2253

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜