POJ 2240 ZOJ 1082 Arbitrage 最短路,c++ stl pass g++ tle 难度:0

http://poj.org/problem?id=2240

用log化乘法为加法找正圈

c++ 110ms,g++tle

#include <string> #include <map> #include <iostream> #include <cmath> #include <cstring> #include <queue> using namespace std; const int maxn = 50; bool vis[maxn]; double chg[maxn][maxn]; double dis[maxn]; int e[maxn][maxn],deg[maxn]; map<string,int> idmp; int n,m; const double inf = 0x3fffffff;queue<int> que; bool hasloop(int s){while(!que.empty())que.pop();que.push(s);vis[s] = true;int cnt = 0;while(!que.empty()){cnt ++;s = que.front();que.pop();vis[s] = false;for(int i = 0;i < deg[s];i++){int t = e[s][i];if(dis[t] < dis[s] + chg[s][t]){dis[t] = dis[s] + chg[s][t];que.push(t);vis[t] = true;}}if(cnt > n * n)return true;}return false; }int main(){int ti = 0;while(cin>>n && n && ++ti){idmp.clear();for(int i = 0;i < n;i++){dis[i] = -inf;for(int j = 0;j < n;j++)chg[i][j] = -inf;}memset(vis,false,sizeof vis);memset(deg,0,sizeof deg);for(int i = 0;i < n;i++){string tmp;cin>>tmp;idmp[tmp] = i;}cin>>m;for(int i = 0;i < m;i++){string sf,st;double change;cin>>sf>>change>>st;change = log(change);int f = idmp[sf];int t = idmp[st];chg[f][t] = change;e[f][deg[f]++] = t;}bool fl = false;for(int i = 0;i < n;i++){if(dis[i] == -inf){dis[i] = 1;if(hasloop(i)){fl = true;break;}}}cout << "Case " << ti << ": ";if(fl)cout << "Yes" <<endl;else cout << "No" << endl;}return 0; }

　　

转载于:https://www.cnblogs.com/xuesu/p/4754667.html

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的POJ 2240 ZOJ 1082 Arbitrage 最短路,c++ stl pass g++ tle 难度:0的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。