Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

好象明白了,如果所有的点都有了,但还要去建,这样吗?太变态了,但我的程序试了一下好象是这样的

Posted by zerocool_08 at 2005-10-12 14:04:14 on Problem 2607
In Reply To:bingo Posted by:frkstyc at 2005-10-12 13:58:56
#include "stdio.h"
#define max  100000000
int location[510]={0},b[510][510]={0},c[510];
int main()
{
    int   n,m,i,j,k,nn,c1,c2,len,temp,max1,max2;
    scanf("%d%d",&n,&m);
    for(i=0;i<=m;i++)   for(j=0;j<=m;j++)  
    {     if(i!=j)  
               b[i][j]=max;
          else
               b[i][j]=0;
    }    
    for(i=0;i<n;i++){
        scanf("%d",&nn);
        location[nn]=1;
    }
    while(scanf("%d %d %d",&c1,&c2,&len)==3&&c1){
        b[c1][c2]=b[c2][c1]=len;
    }  
   for(i=1;i<=m;i++)
   {  
         if(!location[i])
         {
            for(j=1;j<=m;j++) 
            for(k=1;k<=m;k++)
                    {
            if(b[j][k]>b[j][i]+b[i][k])
                   b[j][k]=b[k][j]=b[j][i]+b[i][k];
                           }  
            }    
    }               
    for(i=1;i<=m;i++)
       c[i]=max;
    for(i=1;i<=m;i++)
        if(location[i])
            for(j=1;j<=m;j++){
                if(i==j)
                  c[i]=0;
                else
                  c[j]=(c[j]<b[i][j]? c[j]:b[i][j]);
              }         
      max1=1000000,max2=0,temp=0;
    for(i=1;i<=m;i++)
    {
        if(!location[i])     //如果不去掉这个,就WA,但是把temp一开始设为1
          {                  //去掉也AC
              for(j=1;j<=m;j++)
                  if(i!=j){
                    k=(c[j]<b[i][j]? c[j] : b[i][j]);
                    max2=(max2>k? max2 :  k);
                }   
       if(max1>max2)
           max1=max2,temp=i;
       }
       max2=0;
    }
  printf("%d\n",temp);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator