zoj 1857 || poj 2607

/*
zoj_1857       
     ，      ~
  ： n  ，       house，         fire station（fs）。         fs，  
        house        fs       。

Process：
1.      floyd ，         。
2.  MLE，      ，zoj TLE ，poj wa
3.    mark     （   2），   zoj TLE,poj AC（2000 ms）
4.           spfa  ，     spfa，     spfa     。
  poj AC，     4000 ms，zoj  TLE 。。
5.       spfa        ，    spfa     if( dist[i]>dist[temp]+map[temp][i] )
           ，    if( map[temp][i]!=inf && dist[i]>dist[temp]+map[temp][i] )，   
  poj  （1000 ms），zoj     ，  ~
  
  ：
1.sscanf   
2.spfa
3.  spfa+            ，    。

*/
//  1：spfa+    （1000 ms）
#include <iostream>
#include <cstdio>
#include <string.h>
#include <limits.h>
#include <queue>
#define inf 99999999
#define N 510
using namespace std;
int flag[N];
int ori[N],dist[N];
int map[N][N];

void inint()
{
    int i,j;
    for( i=0;i<N;i++ )
    {
        for( j=0;j<N;j++ )
        {
            if( i==j ) map[i][j]=0;
            else map[i][j]=inf;
        }
        ori[i]=INT_MAX;
    }
    memset( flag,0,sizeof(flag) );
}

void spfa( int sta,int n )
{
    queue <int>q;
    int hash[N],temp,i;
    memset( hash,0,sizeof(hash) );
    for( i=0;i<=n;i++ )
        dist[i]=INT_MAX;
    dist[sta]=0;
    q.push( sta );
    hash[sta]=1;
    while( !q.empty() )
    {
        temp=q.front();   q.pop();
        hash[temp]=0;
        for( i=1;i<=n;i++ )
        {
            if( map[temp][i]!=inf && dist[i]>dist[temp]+map[temp][i] ) //     map[temp][i]!=inf,TLE 
            {
                dist[i]=dist[temp]+map[temp][i];
                if( hash[i]==0 )    hash[i]=1 , q.push(i);
            }
        }
    }
 }

int findmax( int id,int n )
{
    int temp,i,maxi;
    maxi=-1;
    spfa( id,n );
    for( i=1;i<=n;i++ )
        if( !flag[i] )
        {
            temp=ori[i];
            if( dist[i]<temp ) temp=dist[i];
            if( maxi<temp ) maxi=temp;
        }
    return maxi;
}

int main()
{
    //freopen( "AAA_a.txt","r",stdin );
    int n,m,temp,i,j;
    int a,b,v,mini,mark;
    char str[100];
    while( scanf("%d%d",&n,&m)!=EOF )
    {
        inint();
        for( i=0;i<n;i++ )
            scanf( "%d",&temp ) , flag[temp]=1 ;
        getchar();
        while( gets(str) && strlen(str) )
        {
            sscanf( str,"%d%d%d",&a,&b,&v );
            map[a][b]=map[b][a]=v;
        }
        for( i=1;i<=m;i++ )
            if( flag[i] )
            {
                spfa( i,m );
                for( j=1;j<=m;j++ )
                    if( ori[j]>dist[j] )
                        ori[j]=dist[j];
            }
        mini=INT_MAX;
        mark=1;
        for( i=1;i<=m;i++ )
            if( !flag[i] )
            {
                if( mini>( temp=findmax( i,m ) ) )
                    mini=temp , mark=i ;
            }
        printf( "%d
",mark );
    }
    return 0;
}

//  2：floyd+    （2000 ms）
//poj AC,zoj TLE
#include <iostream>
#include <cstdio>
#include <string.h>
#include <limits.h>
#define inf 99999999
#define N 510
using namespace std;
bool flag[N];
int map[N][N];
int dist[N][N][2];
int ori[N];

void inint()
{
    int i,j;
    for( i=0;i<N;i++ )
    {
        for( j=0;j<N;j++ )
        {
            if( i==j ) map[i][j]=0;
            else map[i][j]=inf;
        }
        ori[i]=INT_MAX;
    }
    memset( flag,0,sizeof(flag) );
}

void floyd( int n )
{
    int i,j,k;
    for( i=0;i<=n;i++ )
        for( j=0;j<=n;j++ )
            dist[i][j][0]=map[i][j];
    for( k=1;k<=n;k++ )
    {
        for( i=1;i<=n;i++ )
            for( j=1;j<=n;j++ )
            {
                dist[i][j][1]=dist[i][j][0];
                if( dist[i][j][1]>dist[i][k][0]+dist[k][j][0] )
                    dist[i][j][1]=dist[i][k][0]+dist[k][j][0];
            }
        for( i=1;i<=n;i++ )
            for( j=1;j<=n;j++ )
                dist[i][j][0]=dist[i][j][1];
    }
}

int findmax( int id,int n )
{
    int temp,i,maxi;
    maxi=-1;
    for( i=1;i<=n;i++ )
        if( !flag[i] )
        {
            temp=ori[i];
            if( dist[i][id][0]<temp ) temp=dist[i][id][0];
            if( maxi<temp ) maxi=temp;
        }
    return maxi;
}

int main()
{
    //freopen( "AAA_a.txt","r",stdin );
    int n,m,temp,i,j;
    int a,b,v,mini,mark;
    char str[100];
    while( scanf("%d%d",&n,&m)!=EOF )
    {
        inint();
        for( i=0;i<n;i++ )
            scanf( "%d",&temp ) , flag[temp]=1 ;
        getchar();
        while( gets(str) && strlen(str) )
        {
            sscanf( str,"%d%d%d",&a,&b,&v );
            map[a][b]=map[b][a]=v;
        }
        floyd(m);
        for( i=1;i<=m;i++ )
        {
            if( !flag[i] )
            {
                for( j=1;j<=m;j++ )
                    if( flag[j] && ori[i]>dist[i][j][0] )
                        ori[i]=dist[i][j][0];
            }
            else ori[i]=0;
        }
        mini=INT_MAX;
        mark=1;     //       ，         fire station   
        for( i=1;i<=m;i++ )
            if( !flag[i] )
            {
                if( mini>( temp=findmax( i,m ) ) || mini==INT_MAX )
                    mini=temp , mark=i ;
            }
        printf( "%d
",mark );
    }
    return 0;
}