http://acm.hdu.edu.cn/showproblem.php?pid=1874最短路径问题,经典的Dijsktra嘛。Floyd解决多源点问题,这里是单源点就行。因为可能有重边,而且数据范围也不大,就选用邻接矩阵来储存了。
d[i]表示当前i所找到的最短路径,f[i]记录集合:
#include<stdio.h>
int n,m,maxx=100000000,q[203][203];
int dijsktra(int s,int t)
{
int d[203],f[203],i,j,min,minj;
for (i=1;i<=n;i++)
{
d[i]=maxx;
f[i]=1;
}
d[s]=0; //这里害我wa了很多次。切记
for (i=1;i<=n;i++)
{
min=maxx;
for (j=1;j<=n;j++)
if (f[j]&&d[j]<min)
{
min=d[j];
minj=j;
}
if (minj==t)
return min;
f[minj]=0;
for (j=1;j<=n;j++)
if (f[j]&&d[j]>d[minj]+q[minj][j])
{
d[j]=d[minj]+q[minj][j];
}
}
return -1;
}
int main()
{
int i,j,s,t,k,ans,a,b,c;
while (scanf("%d%d",&n,&m)==2)
{
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
q[i][j]=maxx;
q[i][i]=0;
}
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if (c<q[a+1][b+1])
{
q[a+1][b+1]=c;
q[b+1][a+1]=c;
}
}
scanf("%d%d",&s,&t);
ans=dijsktra(s+1,t+1);
printf("%d\n",ans);
}
}
无语了,这个wa了不知道多少次。结果就是d[s]习惯性地打成d[1]了,这个,要注意呀!重边也需要考虑的哦。