自己写了一个,不过贴一个Waterloo的标程,突然喜欢上这种风格了
#include <stdio.h>
#include <math.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
double z, x[203], y[203], d[202][202];
int i,j,k,n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
main()
{
for (i=0;i<202;i++) for (j=0;j<202;j++) d[i][j] = 1e99;
n=2;
scanf("%lf%lf",&x[0],&y[0]);
scanf("%lf%lf",&x[1],&y[1]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(1)
{
if (2 != scanf("%lf%lf",&x[n],&y[n])) break;
n++;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(1)
{
scanf("%lf%lf",&x[n],&y[n]);
if (x[n] < 0) break;
z = hypot(x[n]-x[n-1],y[n]-y[n-1]);
if (z < d[n-1][n]) d[n-1][n] = d[n][n-1] = z;
n++;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0;i<n;i++) for (j=0;j<n;j++)
{
if (d[i][j] > 1e98) d[i][j] = 4*hypot(x[i]-x[j], y[i]-y[j]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for (i=0;i<n;i++) for (j=0;j<n;j++) for (k=0;k<n;k++)
{
if (d[j][i]+d[i][k] < d[j][k]) d[j][k] = d[j][i]+d[i][k];
}
printf("%0.0lf\n",d[0][1]/40000*60);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)