http://acm.hdu.edu.cn/showproblem.php?pid=1874最短路徑問(wèn)題，經(jīng)典的Dijsktra嘛。Floyd解決多源點(diǎn)問(wèn)題，這里是單源點(diǎn)就行。因?yàn)榭赡苡兄剡叄覕?shù)據(jù)范圍也不大，就選用鄰接矩陣來(lái)儲(chǔ)存了。
d[i]表示當(dāng)前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);
}
}
無(wú)語(yǔ)了，這個(gè)wa了不知道多少次。結(jié)果就是d[s]習(xí)慣性地打成d[1]了，這個(gè)，要注意呀！重邊也需要考慮的哦。