首页 > 代码库 > zoj1857Fire Station最短路

zoj1857Fire Station最短路

2024-07-17 19:25:28   217人阅读

　　乱搞题。就是输入有点问题，我开始用的 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;}

 


联系
我们