>  #include <iostream>
>  using namespace std;
>  
>  int map[501][501];
>  int fire[100];
>  int n,m;
>  
>  void Floyd() // 求出全源最短路径; 
>  {
> 	for(int i=1;i<=n;i++)
> 	   for(int j=1;j<=n;j++)
> 	      for(int k=1;k<=n;k++)
> 	         if( (map[j][i]+map[i][k]<map[j][k]||map[j][k]==-1) && map[j][i]!=-1 && map[i][k]!=-1 && j!=k )
> 				map[j][k] = map[j][i] + map[i][k];
>  }
>  
>  int main()
>  {
>     bool arrived[501];
>     while(cin>>m>>n)
>     {
>        memset(arrived,false,sizeof(arrived));
>        for(int i=0;i<m;i++)  // 读入救火站 
>        {
>           cin>>fire[i];
>           arrived[fire[i]] = true;
>        }
>        
>        for(int i=0;i<=n;i++)  // 初始化地图 
>        {
>           for(int j=0;j<=n;j++)
>              map[i][j] = -1;
>        }
>        
>        int t1,t2,t3;
>        for(int i=0;i<n;i++)  // 读入地图 
>        {
>           cin>>t1>>t2>>t3;
>           map[t1][t2] = t3;
>           map[t2][t1] = t3;
>        }
>        
>        Floyd(); // 求出全源最短路径; 
>   /*     
>        for(int i=1;i<=n;i++)
>        {
>           for(int j=1;j<=n;j++)
>              cout<<map[i][j]<<" ";
>           cout<<endl;
>        }
>   */
>        int result[501];
>        int all = 0;
>        for(int i=1;i<=n;i++) // 求出现有的各点到救火站最短距
>        {
>           int sum = 999999;
>           for(int j=0;j<m;j++)
>           {
>              if(i==fire[j])
>              {
>                 sum = 0;
>                 break;
>              }
>              if(sum>map[i][fire[j]]) sum = map[i][fire[j]];
>           }
>           result[i] = sum;
>           all = all + sum;
>        }
>   /*
>        cout<<all<<endl;
>        for(int i=1;i<=n;i++) cout<<result[i]<<" ";
>        cout<<endl;
>   */
>        int maxn = 999999;
>        int res;
>        for(int i=1;i<=n;i++) // 一个一个枚举 
>        {
>           if(arrived[i]==true) continue;
>           int temp = all;
>           int sum = 999999;
>           for(int j=1;j<=n;j++)
>           {
>              if(i==j) temp = temp - result[i];
>              else if(map[j][i]<result[j]) temp = temp - result[j] + map[j][i];
>           }
>           //cout<<i<<" "<<temp<<endl;
>           if(temp<maxn)
>           {
>              maxn = temp;
>              res = i;
>           }
>        }
>        //cout<<maxn<<endl;
>        cout<<res<<endl;
>     }
>  }

• ft~ (0) number 2005-09-18 14:02:56
• 到底哪里理解不对了，555~~~ (70) jinmingyan 2005-09-18 16:12:14