POJ 1860 Currency Exchange 最短路 难度:0
http://poj.org/problem?id=1860#include <cstdio>
//#include <queue>
//#include <deque>
#include <cstring>
using namespace std;
#define MAXM 202
#define MAXN 101
int n,m;
int first;
int next;
int pto;
double earn;
int start;
double d;
double cost;
bool vis;
void addedge(int from,int to,double fromcost,double fromearn,int index){
next=first;
pto=to;
cost=fromcost;
earn=fromearn;
first=index;
}
bool input(){
bool fl=false;
memset(first,-1,sizeof(first));
double double1;
scanf("%d %d %d %lf",&n,&m,&start,&double1);
d=double1;
double fromc,toc,frome,toe;
int from,to;
for(int i=0;i<m;i++){
scanf("%d %d %lf %lf %lf %lf",&from,&to,&frome,&fromc,&toe,&toc);
addedge(from,to,fromc,frome,2*i);
addedge(to,from,toc,toe,2*i+1);
if(from==start&&frome>0.999999){
fl=true;
}
else if(to==start&&toe>0.999999){
fl=true;
}
}
return fl;
}
int que;
int quehead;
int quetail;
void pushback(int inse){
que=inse;
quetail=(quetail+1)%MAXM;
vis=true;
}
void pushfront(int inse){
quehead=(quehead-1+MAXM)%MAXM;
que=inse;
vis=true;
}
int pop(){
int ans=que;
quehead=(quehead+1)%MAXM;
vis=false;
return ans;
}
bool find_loop(){
if(!input())return false;
pushback(start);
while(quehead!=quetail){
int from=pop();
int p=first;
while(p!=-1){
int to=pto;
double dtemp1;
if((dtemp1=(d-cost)*earn)>d){
d=dtemp1;
if(!vis){
if(d>d])pushfront(to);
else pushback(to);
}
if(to==start){
return true;
}
}
p=next;
}
}
return false;
}
int main(){
if(find_loop()){
printf("YES\n");
}
else printf("NO\n");
}
页:
[1]