真是气skr人。。没把d[]换成double。。。de了一上午的bug//

记得用G++提交啊


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

题意:告诉你n个点,m条路。起始点s,还有初始金额money。每条路表示从a->b的汇率和佣金以及b->a的汇率和佣金。你在该点所得是(本金-佣金)*汇率。问你这个人能不能赚钱。

题解:spfa套一下//。记得d[]换成double。具体的看看代码。QWQ。

代码:

 #include<iostream>
#include<stack>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn = ; struct node{
int to;
double r;
double c;
}; vector< node > e[maxn]; int n,m,num;
double money;
double d[maxn];
int inq[maxn]; bool spfa(int s){
for(int i = ; i <= n ;i++){
inq[i] = d[i] = ;
}
queue<int>Q;
Q.push(s);
d[s] = money;
inq[s] = ;
while( !Q.empty() ){
int now = Q.front();
Q.pop();
inq[now] = ;
for(int i = ; i < e[now].size() ; i++){
double rate = e[now][i].r;
double commis = e[now][i].c;
int v = e[now][i].to; if(d[v] < (d[now] - commis) * rate){
d[v] = (d[now] - commis) * rate;
if(inq[v] == ){
inq[v] = ;
Q.push(v);
}
} if(d[s] > money){
return true;
}
} }
return false;
} int main() {
scanf("%d%d%d%lf",&n,&m,&num,&money);
int x,y;
double r,c;
while(m--){
scanf("%d%d%lf%lf",&x,&y,&r,&c);
e[x].push_back((node){y,r,c});
scanf("%lf%lf",&r,&c);
e[y].push_back((node){x,r,c});
}
if(spfa(num))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl; return ;
}

最新文章

  1. 自己动手模拟开发一个简单的Web服务器
  2. iOS 十六进制的颜色值转换为UIColor
  3. 利用js刷新页面方法
  4. JS 对数组的常用处理
  5. java 操作Excel表 创建 查看 修改
  6. HttpServletRequest常用获取URL的方法
  7. 「ubuntu」通过无线网络安装Ubuntu Server,启动系统后如何连接无线网络
  8. 2016年12月10日 星期六 --出埃及记 Exodus 21:5
  9. Java_JDK_TreeMap
  10. VC++6.0连接Access数据库
  11. Python Tutorial学习(十一)-- Brief Tour of the Standard Library – Part II
  12. 提高你的Java代码质量吧:让我们疑惑的字符串拼接方式的选择
  13. objective-C nil,Nil,NULL 和NSNull的小结
  14. UVA 11464 Even Parity(递归枚举)
  15. ASP.NET AJAX简明教程
  16. Akka(42): Http:身份验证 - authentication, autorization and use of raw headers
  17. 一统江湖的大前端(4)shell.js——穿上马甲我照样认识你
  18. Python的简单介绍
  19. linux 硬链接 软链接
  20. C++语言实现-邻接矩阵

热门文章

  1. ASP.NET Core学习——2
  2. 提升R代码运算效率的11个实用方法
  3. Leetcode刷题——007.整数反转
  4. UVA 1525 Falling Leaves
  5. PAT_A1062#Talent and Virtue
  6. FreeBSD_11-系统管理——{Part_a-bhyve}
  7. 20140610 PP中可以绘制表格;PPT组合之后再加效果
  8. js中常用的正则表达式
  9. 567. Permutation in String【滑动窗口】
  10. 解析TextView中的URL等指定特殊字符串与点击事件