提交时，注意选择所期望的编译器类型。
Thinking:
Using Floyd Algorithm to fix this problem.
#include<iostream>
#include<algorithm>
#define infiniteDistance 9999
using namespace std;
int findMaxDistance(int range,int **route)//find the max element which in the route array
{
int i,j,max=0;
for(i=0;i<range;i++)
for(j=0;j<range;j++)
if(route[i][j]>max)
max=route[i][j];
return max;
}
void Floyd(int **route,int nCity)//Floyd Algorithm
{
int transit,start,target;
for(transit=0;transit<nCity;transit++)
for(start=0;start<nCity;start++)
for(target=0;target<nCity;target++)
if(route[start][target]>route[start][transit]+route[transit][target])
route[start][target]=route[start][transit]+route[transit][target];
}
void init(int **route,int nCity)//initialize
{
int i,j;
for(i=0;i<nCity;i++)
for(j=0;j<nCity;j++)
if(i!=j)//At the beginning,initialize the distance between each pair of those city are infinity.
route[i][j]=infiniteDistance;
}
void input(int **route,int nCity)
{
int i,city1,city2,distance;
for(i=0;i<nCity;i++)
{
cin>>city1>>city2>>distance;
route[city1-1][city2-1]=route[city2-1][city1-1]=distance;//set the route's distance
}
}
int main()
{
int i,j,nCity,cost=0;
cin>>nCity;
int **route=new int*[nCity];
for(i=0;i<nCity;i++)
route[i]=new int[nCity]();
init(route,nCity);
input(route,nCity-1);
Floyd(route,nCity);
for(i=1;i<=findMaxDistance(nCity,route);i++)//To figure out the most expensive cost.
cost+=(i+10);
cout<<cost<<endl;
for(i=0;i<nCity;i++)
delete []route[i];
delete []route;
return 0;
}
原文：http://blog.csdn.net/lc0817/article/details/42835521