首页 > 代码库 > poj 2607 Fire Station (spfa)
poj 2607 Fire Station (spfa)
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.
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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。