最簡單的dijkstra應(yīng)用，別的就不說了 題目鏈接：
http://acm.hdu.edu.cn/showproblem.php?pid=1874
#include<stdio.h>
#include<string.h>
#define MAXN 201
#define MAX 999999
int dist[MAXN][MAXN],x[MAXN];
int main()
{
int n,m,i,j,t,s,d,a,b,time,min;
while(scanf("%d%d",&n,&m)==2)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
dist[i][j]=0;
else
dist[i][j]=MAX;
}
}
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&time);
dist[a][b]=dist[b][a]=time<dist[a][b]?time:dist[a][b];
}
scanf("%d%d",&s,&d);
for(i=0;i<n;i++)
x[i]=dist[s][i];
dist[s][s]=1;
t=0;
while(t!=-1)
{
min=-1;
t=-1;
for(i=0;i<n;i++)
if(dist[i][i]==0&&(min==-1||x[i]<min))
{
min=x[i];
t=i;
}
if(t!=-1)
{
dist[t][t]=1;
for(i=0;i<n;i++)
if(x[i]>x[t]+dist[t][i])
{
x[i]=x[t]+dist[t][i];
}
}
}
if(x[d]<MAX)
printf("%d\n",x[d]);
else
printf("-1\n");
}
return 0;
}
posted on 2010-10-06 09:23
孟起 閱讀(543)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
圖論