网站服务器哪些好,用php做的录入成绩的网站,腾讯云 wordpress博客,十堰网站网站建设感觉最短路好神奇呀#xff0c;刚开始我都 没想到用最短路 题目#xff1a;http://poj.org/problem?id1860 题意#xff1a;有多种从a到b的汇率#xff0c;在你汇钱的过程中还需要支付手续费#xff0c;那么你所得的钱是 money#xff08;nowmoney-手续费#xff09;*r…感觉最短路好神奇呀刚开始我都 没想到用最短路 题目http://poj.org/problem?id1860 题意有多种从a到b的汇率在你汇钱的过程中还需要支付手续费那么你所得的钱是 moneynowmoney-手续费*rate现在问你有v钱从s开始出发交换钱能不能赚钱 题解这题其实是用bellman_ford的思想通过n-1次松弛后如果还能增加就说明有环 可以使金钱数不断增加。 1 #include iostream2 #includecstdio3 #includecstring4 #includecstdlib5 #includestack6 #includequeue7 #includecmath8 #includealgorithm9 using namespace std;
10 int cnt;
11 double dis[1000];
12 double n,m,v;
13 struct node
14 {
15 int u,v,next;
16 double r,c;
17 }edge[1000];
18
19 void add(int u,int v,double r,double c)
20 {
21 edge[cnt].uu; edge[cnt].vv;
22 edge[cnt].rr; edge[cnt].cc;
23 }
24 int bellman_ford(int s)
25 {
26 int i,j;
27 for(i0; in; i)
28 dis[i]0;
29 dis[s]v; //跟最短路不一样到自己的距离是原来的钱数
30 for(i0; in-1; i)
31 for(j0; jcnt; j)
32 {
33 if(dis[edge[j].v](dis[edge[j].u]-edge[j].c)*edge[j].r)//逆用最短路
34 dis[edge[j].v](dis[edge[j].u]-edge[j].c)*edge[j].r;
35 }
36 for(j0; jcnt; j)
37 if(dis[edge[j].v](dis[edge[j].u]-edge[j].c)*edge[j].r)//如果成立说明有能使钱数增加的环
38 return 1;
39 return 0;
40 }
41 int main()
42 {
43 int s,i,j,a,b;
44 double rab,cab,rba,cba;
45 scanf(%lf%lf%d%lf,n,m,s,v);
46 cnt0;
47 for(i0; im; i)
48 {
49 scanf(%d%d%lf%lf%lf%lf,a,b,rab,cab,rba,cba);
50 add(a,b,rab,cab);
51 add(b,a,rba,cba);
52 }
53 if(bellman_ford(s)) printf(YES\n);
54 else printf(NO\n);
55 return 0;
56 }
57 这个博客http://blog.csdn.net/wangjian8006/article/details/7871753 就是到s的距离大于v了就是YES。 有spfa的代码这个应该理论上更省时间转载于:https://www.cnblogs.com/bfshm/p/3245933.html
