Currency Exchange（货币交换）

memn

　　poj 1860
　　题目大意：给出n货币种类数，从1....n,给出m表示交换货币的地点，s表示源点的编号，v表示起始总钱数，接下来m行，每行6个分别是从a到b和a到b的利率，a到b的费用，b到a的利率，b到a的费用，可以建图了。
　　解决：spfa直接就出来了



#include <iostream>
#include <queue>
using namespace std;
struct node
{
int v;
double w,c;
int next;
};
node e[100000];
const int N=110;
int pos;
int head[N];
int n,m,s;
double tot;
double dist[N];
bool inq[N];
int cnt[N];
void init()
{
for(int i=1;i<=n;i++)
{
dist=-0x2f2f2f2f;//初始化dist最小
cnt=0;
inq=0;
head=-1;
}
}
void addedge(int u,int v,double w,double c)
{
e[pos].v=v;
e[pos].w=w;
e[pos].c=c;
e[pos].next=head;
head=pos++;
}
void spfa()
{
queue<int> q;
int v0=s;
q.push(v0);
dist[v0]=tot;  //初始化源点的dist值即最开始手中的钱
inq[v0]=1;
int v;   //就是一spfa算法
double w,c;
while(!q.empty())
{
v0=q.front();
q.pop();
inq[v0]=0;
for(int i=head[v0];i!=-1;i=e.next)
{
v=e.v;
w=e.w;
c=e.c;
if((dist[v0]-c)* w > dist[v])
{
dist[v]=(dist[v0]-c)* w;
//判断源点的钱是不是增加了，增加就退出了
if(dist>tot){puts("YES");return;}
if(!inq[v])
{
inq[v]=1;
q.push(v);
}
}
}
}
//结束还没退出就不行了
puts("NO");
}
int main()
{
scanf("%d%d%d%lf",&n,&m,&s,&tot);
pos=0;
init();
int a,b;
double r1,c1,r2,c2;
getchar();
for(int i=0;i<m;i++)
{
scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);
addedge(a,b,r1,c1);
addedge(b,a,r2,c2);
}
spfa();
system("pause");
return 0;
}

　　
　　

There can be several points specializing in the same pair of currencies. Each point has its own exchange rates,这句话说明了有重复的边，我干脆用了邻接矩阵，因为之前花费一天时间a了第一道查分约束，用到了邻接矩阵建图，所以这题一次就过了，听顺的，呵呵，再次说明不会的题，实在想不起来了先放放，做其他题找灵感，