POJ 1860 Currency Exchange 最短路 难度:0

njsuntop

　　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[MAXN];
int next[MAXM];
int pto[MAXM];
double earn[MAXM];
int start;
double d[MAXN];
double cost[MAXM];
bool vis[MAXM];
void addedge(int from,int to,double fromcost,double fromearn,int index){
next[index]=first[from];
pto[index]=to;
cost[index]=fromcost;
earn[index]=fromearn;
first[from]=index;
}
bool input(){
bool fl=false;
memset(first,-1,sizeof(first));
double double1;
scanf("%d %d %d %lf",&n,&m,&start,&double1);
d[start]=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[MAXM];
int quehead;
int quetail;
void pushback(int inse){
que[quetail]=inse;
quetail=(quetail+1)%MAXM;
vis[inse]=true;
}
void pushfront(int inse){
quehead=(quehead-1+MAXM)%MAXM;
que[quehead]=inse;
vis[inse]=true;
}
int pop(){
int ans=que[quehead];
quehead=(quehead+1)%MAXM;
vis[ans]=false;
return ans;
}
bool find_loop(){
if(!input())return false;
pushback(start);
while(quehead!=quetail){
int from=pop();
int p=first[from];
while(p!=-1){
int to=pto[p];
double dtemp1;
if((dtemp1=(d[from]-cost[p])*earn[p])>d[to]){
d[to]=dtemp1;
if(!vis[to]){
if(d[to]>d[que[quehead]])pushfront(to);
else pushback(to);
}
if(to==start){
return true;
}
}
p=next[p];
}
}
return false;
}
int main(){
if(find_loop()){
printf("YES\n");
}
else printf("NO\n");
}