首页 > 代码库 > zoj1857Fire Station最短路
zoj1857Fire Station最短路
乱搞题。就是输入有点问题,我开始用的 scanf("%d%d%d",&a,&b,&c) !=EOF 然后就妥妥的秒wa 但是poj 莫名奇妙的过了,这时Gxwar 告诉我zoj我过不了,然后我就过不了。。。可是改了下输入就过了。真是神奇。
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;int dis[555];int dist[555];int Map[555][555];const int INF=0xfffffff;int m;void floyd(){ for(int k=1;k<=m;k++) for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++){ Map[i][j]=min(Map[i][j],Map[i][k]+Map[k][j]); } }}void spfa(int x){ int vis[555]; memset(vis,0,sizeof(vis)); for(int i=1;i<=m;i++) dist[i]= dis[i]; queue<int> q; q.push(x) ; dist[x]= 0 ;vis[x]=1; while(!q.empty()){ int cur= q.front() ;q.pop(); vis[cur]=0; for(int i=1;i<=m;i++){ if(dist[i]>dist[cur]+Map[cur][i]){ dist[i]=dist[cur]+Map[cur][i]; if(!vis[i]){ vis[i]=1;q.push(i); } } } }}int main(){ int n;int a,b,c; int val[555],vis[555]; char str[100]; while(scanf("%d%d",&n,&m)!=EOF){ memset(vis,0,sizeof(vis)); memset(val,0,sizeof(val)); for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) if(i==j) Map[i][j]=0;else Map[i][j]=INF; for(int i=1;i<=m;i++) dis[i]=INF; for(int i=0;i<n;i++){ scanf("%d",&val[i]);vis[val[i]]= 1; dis[val[i]]= 0; } getchar(); while(gets(str)&&strlen(str)){ sscanf(str,"%d%d%d",&a,&b,&c); Map[a][b]=Map[b][a]=c; } floyd(); for(int i=0;i<n;i++){ for(int j=1;j<=m;j++){ if(vis[j]) continue; if(dis[j]>Map[val[i]][j]) dis[j] = Map[val[i]][j]; } } for(int i=0;i<n;i++){ dis[val[i]]=0; } int Max=0; for(int i=1;i<=m;i++) if(dis[i]>Max) Max= dis[i]; int flag=1; for(int i=m;i>=1;i--){ if(vis[i]) continue; int Max1=0; spfa(i); for(int j=1;j<=m;j++){ if(vis[j]) continue; if(dist[j]>Max1) Max1=dist[j]; } if(Max1<=Max){ Max= Max1; flag= i; } } printf("%d\n",flag); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。