POJ 1860Currency Exchange(贝尔曼最短路)

本文主要是介绍POJ 1860Currency Exchange(贝尔曼最短路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：http://poj.org/problem?id=1860

这个题一道很简单的贝尔曼判环的应用，用贝尔曼判环挺方便的。因为把r,c定义成了整型，错了一晚上。。。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>using namespace std;
struct node
{int u, v;double c, r;
} edge[10000];
double x, d[10000];
int n, s, k;
void bfff()
{int i, j, flag, xx;memset(d,0,sizeof(d));d[s]=x;for(i=0; i<n-1; i++){flag=0;for(j=0; j<k; j++){if(d[edge[j].v]<(d[edge[j].u]-edge[j].c)*edge[j].r){d[edge[j].v]=(d[edge[j].u]-edge[j].c)*edge[j].r;flag=1;}}if(!flag)break;}xx=0;for(i=0; i<k; i++){if(d[edge[i].v]<(d[edge[i].u]-edge[i].c)*edge[i].r){xx=1;break;}}if(xx)printf("YES\n");elseprintf("NO\n");
}
int m, u, v;
int main()
{double c1, c2, r1, r2;scanf("%d%d%d%lf",&n,&m,&s,&x);k=0;while(m--){scanf("%d%d%lf%lf%lf%lf",&u,&v,&r1,&c1,&r2,&c2);edge[k].u=u;edge[k].v=v;edge[k].r=r1;edge[k++].c=c1;edge[k].u=v;edge[k].v=u;edge[k].r=r2;edge[k++].c=c2;}//printf("%d %d\n",edge[0].u,edge[0].v);bfff();return 0;
}

这篇关于POJ 1860Currency Exchange(贝尔曼最短路)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---