http://acm.hdu.edu.cn/showproblem.php?pid=2544
#include<stdio.h>
#define Min(a,b) a>b?b:a
#define inf 0x7FFFFFFF
#define M 101
int map[M][M];
int minload[M];
int visit[M];
int main()
{
int n,m,i,j,a,b,dis,start,min,next;
while (scanf("%d%d",&n,&m),n+m)
{
for(i=1;i<=n;i++)
{
visit[i] = 1;
minload[i] = inf;
for(j=1;j<=n;j++)
map[i][j] = inf;
}
while(m--)
{
scanf("%d%d%d",&a,&b,&dis);
map[a][b] = map[b][a] = dis;
}
start = 1;
minload[start] = 0;
visit[start] = 0;
while(start != n)
{
min = inf;
for(i=1;i<=n;i++)
{
if(map[start][i]!=inf)
minload[i] = Min(minload[i],map[start][i]+minload[start]);
if(visit[i] && minload[i]<min)
{
next = i;
min = minload[i];
}
}
start = next;
visit[start] = 0;
}
printf("%d\n",minload[n]);
}
return 0;
}
修改了一下，這個(gè)效率高一點(diǎn)
每個(gè)minload[n]代表n到起點(diǎn)的最短距離
posted on 2009-02-15 14:23
shǎ崽 閱讀(481)
評(píng)論(2) 編輯 收藏 引用