#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;
    }
 }

• 根本就没看题乱搞 (2437) 00448264 2005-09-18 13:49:54
  • ft~ (0) number 2005-09-18 14:02:56
  • 到底哪里理解不对了，555~~~ (70) jinmingyan 2005-09-18 16:12:14