题目链接：
ZJU:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1544
PKU:http://poj.org/problem?id=1860
Description
Input
Output
Sample Input
3 2 1 20.0 1 2 1.00 1.00 1.00 1.00 2 3 1.10 1.00 1.10 1.00
Sample Output
YES
Source
代码如下：
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctype.h>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
#define pi acos(-1.0)
#define INF 0xffffff
#define N 3005
#define M 2005
int Edgehead[N];
int cont[N];
double dis[N];
struct
{
int v,next;
double rate, comm, w;
} Edge[2*M];
bool vis[N];
int k;
int n, m, s;
double val;
void Addedge(int u,int v,double r, double c)
{
Edge[k].next = Edgehead[u];
Edge[k].rate = r;
Edge[k].v = v;
Edge[k].comm = c;
Edge[k].w = 0;
Edgehead[u] = k++;
}
void init()
{
for(int i = 1 ; i <=n ; i++ )//求最长路径开始设为-1
dis[i] = 0;
memset(Edgehead,-1,sizeof(Edgehead));
memset(vis,false,sizeof(vis));
memset(cont,0,sizeof(cont));
}
int SPFA( int start)
{
queue<int>Q;
dis[start] = val;
vis[start] = true;
++cont[start];
Q.push(start);
while(!Q.empty())//直到队列为空
{
int u = Q.front();
Q.pop();
vis[u] = false;
for(int i = Edgehead[u] ; i!=-1 ; i = Edge[i].next)//注意
{
int v = Edge[i].v;
Edge[i].w = (dis[u] - Edge[i].comm)*Edge[i].rate-dis[u];
if(dis[v] < dis[u] + Edge[i].w)
{
dis[v] = dis[u]+Edge[i].w;
if( !vis[v] )//防止出现环，也就是进队列重复了
{
Q.push(v);
vis[v] = true;
}
if(++cont[v] > n)//有负环
return -1;
}
}
}
return 1;
}
int main()
{
int a, b;
double r, c;
while(~scanf("%d%d%d%lf",&n,&m,&s,&val))//n为目的地
{
k = 0;
init();
for(int i = 1 ; i <= m ; i++ )
{
scanf("%d%d",&a,&b);
scanf("%lf%lf",&r,&c);
Addedge(a, b, r, c);//双向链表
scanf("%lf%lf",&r,&c);
Addedge(b, a, r, c);//双向链表
}
if(SPFA(s) == -1)
{
printf("YES\n");
}
else
printf("NO\n");
}
return 0;
}POJ 1860 & ZOJ 1544 Currency Exchange（最短路SPFA）
原文：http://blog.csdn.net/u012860063/article/details/39738181