首页 > 代码库 > POJ2240Arbitrage SPFA+邻接矩阵
POJ2240Arbitrage SPFA+邻接矩阵
坑爹的题,读了好半天才读懂,以为spfa+邻接矩阵就可以秒的,但是一直wa,
调了一个小时才发现,map数组开成int型了,导致精度损失,连样例都没过,
第二个错误是数组开小了,题上说30,我就真的狠耿直的吧数组范围开到30了,
蛋疼,改到35就过了
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> using namespace std; #define INF 0x7f #define maxn 35 double dist[maxn]; double map[maxn][maxn]; int n,m; char name[maxn][1000]; int flag; bool vis[maxn]; void spfa(int s) { memset(vis,0,sizeof(vis)); int i; for(i=1;i<=n;i++) dist[i]=0; dist[s]=1; queue<int>q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=false; //cout<<u<<endl; for(i=1;i<=n;i++) { //cout<<map[u][2]<<" "<<dist[2]<<" "<<dist[u]*map[u][2]<<endl; if(map[u][i]!=0&&dist[i]<dist[u]*map[u][i]) { //cout<<u<<" "<<i<<" "<<map[u][i]<<endl; dist[i]=dist[u]*map[u][i]; if(!vis[i]) { vis[i]=true; q.push(i); } } } } if(dist[s]>1) flag=1; } int main() { int i,j; double num; int kase=0; char str[1000],str1[1000]; while(cin>>n) { if(n==0) break; flag=0; for(i=1;i<=n;i++) { scanf("%s",name[i]); } cin>>m; memset(map,0,sizeof(map)); for(int k=1;k<=m;k++) { scanf("%s %lf %s",str,&num,str1); for(i=1;strcmp(name[i],str);i++); for(j=1;strcmp(name[j],str1);j++); map[i][j]=num; } for(i=1;i<=n;i++) { spfa(i); if(flag) break; } if(flag) printf("Case %d: Yes\n",++kase); else printf("Case %d: No\n",++kase); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。