学步园

题目链接:  http://poj.org/problem?id=2607

               http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=857

其实啥都不想说,万恶的题意,万恶到输入都不给说明...

minimize the maximum distance from any intersection to the nearest fire station.

好吧, 这一句把我绕得~看了别人的才知道是这么个状况,加入的fire station不是为整个city服务

而是为了几个别complaint的村庄而计划的,,,

上代码,注释都赖得写了:

　zoj

   poj

#include<cstdio><br /> #include<cstring><br /> #include<queue><br /> using namespace std;<br /> #define M 508<br /> #define N 20008<br /> #define INF 0x7fffffff<br /> typedef struct talQNode{<br /> int v,c;<br /> bool operator < (const talQNode &a) const<br /> {<br /> return a.c<c;<br /> }<br /> }QNode;<br /> typedef struct{<br /> int u,v,c;<br /> int next;<br /> }Edge;<br /> Edge edge[N];<br /> int head[M];<br /> int dis[M],disl[M];<br /> bool vis[M],inq[M];<br /> int fire[M];<br /> int f,n,e;<br /> priority_queue<QNode>q;</p> <p>void AddEdge(int u,int v,int c)<br /> {<br /> edge[e].u=u;edge[e].v=v;edge[e].c=c;<br /> edge[e].next=head[u];head[u]=e++;<br /> edge[e].v=u;edge[e].u=v;edge[e].c=c;<br /> edge[e].next=head[v];head[v]=e++;<br /> }<br /> void Dijkstra(int f)<br /> {<br /> QNode cur,next;<br /> int u,v,tmp;<br /> memset(vis,false,n+1);<br /> cur.v=f;cur.c=0;<br /> q.push(cur);<br /> while(!q.empty()){<br /> cur=q.top();q.pop();<br /> u=cur.v;<br /> if(vis[u]) continue;<br /> dis[u]=cur.c;<br /> vis[u]=true;<br /> for(tmp=head[u];tmp!=-1;tmp=edge[tmp].next){<br /> v=edge[tmp].v;<br /> if(vis[v]) continue;<br /> if(dis[v]-dis[u]>edge[tmp].c){<br /> dis[v]=dis[u]+edge[tmp].c;<br /> next.v=v;next.c=dis[v];<br /> q.push(next);<br /> }<br /> }<br /> }<br /> }</p> <p>int SPFA(int f)<br /> {<br /> QNode cur,next;<br /> int rel,u,v,tmp;<br /> memset(inq,false,n+1);<br /> cur.v=f;cur.c=0;<br /> inq[f]=true;disl[f]=0;<br /> q.push(cur);<br /> while(!q.empty()){<br /> cur=q.top();q.pop();<br /> u=cur.v;<br /> inq[u]=false;<br /> for(tmp=head[u];tmp!=-1;tmp=edge[tmp].next){<br /> v=edge[tmp].v;<br /> if(disl[v]-disl[u]>edge[tmp].c){<br /> disl[v]=disl[u]+edge[tmp].c;<br /> if(!inq[v]){<br /> inq[v]=true;<br /> next.v=v;<br /> next.c=disl[v];<br /> q.push(next);<br /> }<br /> }<br /> }<br /> }<br /> rel=0;<br /> for(int i=1;i<=n;i++){<br /> if(disl[i]>rel)<br /> rel=disl[i];<br /> }<br /> return rel;<br /> }<br /> void InitDis()<br /> {<br /> int i;<br /> for(i=0;i<=n;i++)<br /> dis[i]=INF;<br /> for(i=0;i<f;i++)<br /> Dijkstra(fire[i]);<br /> }<br /> int Find()<br /> {<br /> int ret=0,i,min=INF,tmp;<br /> for(i=1;i<=n;i++){<br /> memmove(disl,dis,4*(n+1));<br /> tmp=SPFA(i);<br /> if(tmp<min){<br /> ret=i;<br /> min=tmp;<br /> }<br /> }<br /> return ret;<br /> }<br /> int main()<br /> {<br /> int i,u,v,c;<br /> char s[108];</p> <p> while(~scanf("%d%d",&f,&n)){<br /> memset(head,-1,sizeof(head));<br /> e=0;<br /> for(i=0;i<f;i++)<br /> scanf("%d",fire+i);<br /> getchar();<br /> while(gets(s)&&s[0]){<br /> sscanf(s,"%d%d%d",&u,&v,&c);<br /> AddEdge(u,v,c);<br /> }<br /> InitDis();<br /> printf("%d/n",Find());<br /> }<br /> return 0;<br /> }