POJ 2607 Fire Station（Floyd）

설명 은 n 개 도시 가 있 는데 그 중에서 m 개 도 시 는 소방 서 가 있 고 일부 도시 간 에 도로 가 통행 되 고 있 습 니 다. 현 재 는 모든 도시 가 소방 서 에서 의 최대 거 리 를 최소 화하 기 위해 소방 서 를 새로 만들어 야 합 니 다. 이 최소 거 리 를 출력 하 는 Input 첫 줄 의 두 정수 m 와 n 은 기 존의 소방 서 의 도시 개수 와 총 도시 개 수 를 나타 냅 니 다.두 번 째 줄 m 의 정 수 는 소방 서 의 도시 번호 가 있 음 을 나타 낸다. 그 다음 에 줄 마다 세 개의 정수 u, v, c 는 도시 u 와 도시 v 사이 에 길이 가 c 인 도로 가 있 음 을 나타 내 고 파일 끝으로 도로 입력 을 끝 낸다.(n < = 500) 출력 이 최소 화 된 도시 거리 소방 서 최대 거리 Sample Input 1 6 2 1 2 10 2 3 10 4 10 5 6 10 10 Sample Output 5 Solution

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 501
#define INF 0x3f3f3f3f
int n,m,cost[maxn][maxn],dis[maxn],vis[maxn];
int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        int u,v,c;
        for(int i=1;i<=n;i++)
        {
            dis[i]=INF;vis[i]=0;
            for(int j=1;j<=n;j++)
                cost[i][j]=i==j?0:INF;
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&u);
            dis[u]=0;
            vis[u]=1;
        }
        while(~scanf("%d%d%d",&u,&v,&c))
            cost[u][v]=cost[v][u]=c;
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)   
                for(int j=1;j<=n;j++)   
                    cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
        for(int i=1;i<=n;i++)
            if(vis[i])
                for(int j=1;j<=n;j++)
                    dis[j]=min(dis[j],cost[i][j]);
        int ans=INF,pos;
        for(int i=1;i<=n;i++)
        {
            int temp=-1;
            for(int j=1;j<=n;j++)
                temp=max(temp,min(dis[j],cost[i][j]));
            if(ans>temp)ans=temp,pos=i;
        }
        printf("%d
",pos);
    }
    return 0;
}