现在的位置: 首页 > 综合 > 正文

最短路

2012年01月29日 ⁄ 综合 ⁄ 共 698字 ⁄ 字号 评论关闭
#include<stdio.h>
#include
<string.h>
#include
<stdlib.h>
const int inf=0x7fffffff;
int map[100][100],visit[100],dis[100];

int dij(int N)
{
int i;
/*
for(i=1;i<=N;i++)
{
dis[i]=map[i][N];

visit[i]=0;
}
*/
for ( i = 1; i <= N; ++ i ) {
dis[i]
= inf;
visit[i]
= 0;
}
dis[
1]=0;


for(i=1;i<=N;i++)
{
int t=inf,k,j;
for(j=1;j<=N;j++)
{
if(t>dis[j]&&!visit[j])
{
t
=dis[j];
k
=j;
}
}
visit[k]
=1;
for(j=1;j<=N;j++)
{
if(map[k][j]!=inf&&dis[j]>map[k][j]+dis[k]&&!visit[j])
dis[j]
=dis[k]+map[k][j];
//if(j==N)

}

}
return dis[N];

}




int main( )
{
int N,M;
while(scanf("%d%d",&N,&M)!=EOF&&(N||M))
{
int x,y,time,i,j;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{
map[i][j]
=inf;
}
for(i=1;i<=M;i++)
{
scanf(
"%d%d%d",&x,&y,&time);
map[x][y]
=map[y][x]=time;
}
printf(
"%d\n",dij(N));
}
//system("pause");
return 0;
}

抱歉!评论已关闭.