The Fourth Dimension Space

枯葉北風(fēng)寒，忽然年以殘，念往昔，語(yǔ)默心酸。二十光陰無(wú)一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢(mèng)令

導(dǎo)航

<

2022年12月

>

日

一

二

三

四

五

六

27

28

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

統(tǒng)計(jì)

隨筆 - 414
文章 - 13
評(píng)論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

搜索

閱讀排行榜

評(píng)論排行榜

再看floyd

#include<iostream>

#include<cstdio>

using namespace std;

#define numVertices 500

#define MAXNUM 999999999

double weight[numVertices][numVertices];

double a[numVertices][numVertices];

int path[numVertices][numVertices];

void floyd()

{

int i,j,k;

for (i = 0; i < numVertices; i++)

{

for (j = 0; j < numVertices; j++)

{

a[i][j] = weight[i][j];

if (i != j && a[i][j] < MAXNUM)

{

path[i][j] = i;

}

else

{

path[i][j] = -1;

}

for (k = 0; k < numVertices; k++)

{

for (i = 0; i < numVertices; i++)

{

for (j = 0; j < numVertices; j++)

{

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

{

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

path[i][j] = path[k][j];

}

int p;

int ans[500];

int f;

void getpath(int i,int j)

{

p=0;

f=0;

int k;

k=path[i][j];

while(true)

{

if(k==-1)

{

f=1;

printf("No answer\n");

return ;

}

else if(k==i)

{

printf("最短路徑長(zhǎng)度為: %lf ",a[i][j]);

printf("路線為：");

ans[++p]=k;

for(int ll=p;ll>=1;ll--)

printf("%d ",ans[ll]+1);

printf("%d\n",j+1);

return ;

}

else

{

ans[++p]=k;

k=path[i][k];

}

int main()

{

int n;

int i,j,k;

int a,b;

scanf("%d",&n);

for(j=0;j< numVertices ;j++)

for(k=0;k< numVertices ;k++)

weight[j][k]=weight[k][j]=MAXNUM;

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

{

double c;

cin>>a>>b>>c;

weight[a-1][b-1]=weight[b-1][a-1]=c;

}

floyd();

int q;

cin>>q;

for(j=1;j<=q;j++)

{

cin>>a>>b;

getpath(a-1,b-1);

}

return 0;

}

posted on 2010-05-30 17:09 abilitytao 閱讀(226) 評(píng)論(0) 編輯收藏引用

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




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

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