首页 > 代码库 > spfa-poj1860
spfa-poj1860
spfa详细图解:http://www.360doc.com/content/13/1208/22/14357424_335569176.shtml
此题循环将交换后变多的货币加入到队列中,结束条件是队列中没有元素或是起始货币交换后的数量已经超过了起始数量
#include <cstdio> #include <iostream> #include <cstring> #include <queue> using namespace std; int c2cnum[110];//记录从i货币有多少种交换方式 int c2cj[110][110];//记录第i货币的第n个交换方式是交换的哪种货币 double c2cr[110][110];//记录i货币第n种交换方式汇率,i从零开始 double c2cc[110][110];//记录i货币第n种交换方式的手续费,i从零开始 double d[110]; int qin[110]; queue<int> q; int main(){ int N,M,S;double V; memset(c2cnum,0,sizeof(c2cnum)); memset(d,0,sizeof(d)); memset(qin,0,sizeof(qin)); cin>>N>>M>>S>>V; int A,B;double RAB,CAB,RBA,CBA ; while(M--){ cin>>A>>B>>RAB>>CAB>>RBA>>CBA ; c2cr[A][c2cnum[A]]=RAB; c2cc[A][c2cnum[A]]=CAB; c2cj[A][c2cnum[A]]=B; c2cnum[A]++; c2cr[B][c2cnum[B]]=RBA; c2cc[B][c2cnum[B]]=CBA; c2cj[B][c2cnum[B]]=A; c2cnum[B]++; } d[S]=V; q.push(S); qin[S]=1; int front; while(q.size()){ front=q.front(); q.pop(); qin[front]=0; for(int i=0;i<c2cnum[front];i++){ //printf("%d %d\n",front,c2cj[front][i]); if(c2cr[front][i]*(d[front]-c2cc[front][i])>d[c2cj[front][i]]){ if(qin[c2cj[front][i]]!=1){ q.push(c2cj[front][i]); qin[c2cj[front][i]]=1; } d[c2cj[front][i]]=c2cr[front][i]*(d[front]-c2cc[front][i]); } } if(d[S]>V)break; } printf("%s\n",d[S]>V?"YES":"NO"); //cin>>N>>M>>S>>V; return 0; }
spfa-poj1860
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。