首页 > 代码库 > poj 2607 Fire Station （spfa）

poj 2607 Fire Station （spfa）

2024-07-21 21:33:08   221人阅读

Fire Station
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 3783 Accepted: 1337

Description

A city is served by a number of fire stations. Some residents have complained that the distance from their houses to the nearest station is too far, so a new station is to be built. You are to choose the location of the fire station so as to reduce the distance to the nearest station from the houses of the disgruntled residents. 
The city has up to 500 intersections, connected by road segments of various lengths. No more than 20 road segments intersect at a given intersection. The location of houses and firestations alike are considered to be at intersections (the travel distance from the intersection to the actual building can be discounted). Furthermore, we assume that there is at least one house associated with every intersection. There may be more than one firestation per intersection. 

Input

The first line of input contains two positive integers: f,the number of existing fire stations (f <= 100) and i, the number of intersections (i <= 500). The intersections are numbered from 1 to i consecutively. f lines follow; each contains the intersection number at which an existing fire station is found. A number of lines follow, each containing three positive integers: the number of an intersection, the number of a different intersection, and the length of the road segment connecting the intersections. All road segments are two-way (at least as far as fire engines are concerned), and there will exist a route between any pair of intersections.

Output

You are to output a single integer: the lowest intersection number at which a new fire station should be built so as to minimize the maximum distance from any intersection to the nearest fire station.

Sample Input

1 6
2
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 1 10

Sample Output

5
题意：就是新建一个消防局使得居民点到消防局的最小值中最大的那个变得更小。若每个点都有消防局，输出1。

思路：用spfa求出原先的消防局到各个点的最短路，然后枚举每个居民点作为消防局，求得答案。

#include"stdio.h"
#include"string.h"
#include"vector"
#include"queue"
#include"iostream"
#include"algorithm"
using namespace std;
#define N 505
#define max(a,b) ((a)>(b)?(a):(b))
const int inf=0x7fffffff;
int a[N],head[N],newd[N],dis[N],q[N];
int t;
struct node
{
    int u,v,w,next;
}e[N*20];
void add(int u,int v,int w)
{
    e[t].u=u;
    e[t].v=v;
    e[t].w=w;
    e[t].next=head[u];
    head[u]=t++;
}
void spfa(int s)   
{
    int i,l,r,u,v;
    bool in[N];
    memset(in,0,sizeof(in));
    l=r=0;
    q[r++]=s;
    newd[s]=0;
    while(l<r)          //循环队列
    {
        u=q[l++%N];
        in[u]=0;
        for(i=head[u];i!=-1;i=e[i].next)
        {
            v=e[i].v;
            if(newd[u]<inf&&newd[v]>newd[u]+e[i].w)
            {
                newd[v]=newd[u]+e[i].w;
                if(!in[v])
                {
                    in[v]=1;
                    q[r++%N]=v;
                }
            }
        }
    }
}
int main()
{
    int i,j,n,f,u,v,w;
    char str[100];
    while(scanf("%d%d",&f,&n)!=-1)
    {
        memset(a,0,sizeof(a));
        memset(head,-1,sizeof(head));
        t=0;
        for(i=0;i<f;i++)
        {
            scanf("%d",&j);
            a[j]=1;
        }
        getchar();
        while(fgets(str,100,stdin)&&strlen(str)-1)     //注意输入
        {
            str[strlen(str)-1]!='\0';
            sscanf(str,"%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        if(f==n)
        {
            printf("1\n");
            continue;
        }
        for(i=1;i<=n;i++)
        {
            if(a[i])
                newd[i]=0;
            else
                newd[i]=inf;
        }
        for(i=1;i<=n;i++)
            if(a[i])
                spfa(i);
        int mmax=-1;
        for(i=1;i<=n;i++)
        {
            mmax=max(mmax,newd[i]);
            dis[i]=newd[i];     //dis保存原先值
        }
        for(i=1;i<=n;i++)
        {
            if(!a[i])
            {
                int tmp=0;
                spfa(i);
                for(j=1;j<=n;j++)
                {
                    tmp=max(tmp,newd[j]);
                }
                if(tmp<mmax)
                {
                    mmax=tmp;
                    f=i;
                }
            }
            memcpy(newd,dis,sizeof(dis));    //恢复原先值
        }
        printf("%d\n",f);
    }
    return 0;
}


poj 2607 Fire Station （spfa）


联系
我们