POJ 1860 Currency Exchange(SPFA+邻接矩阵)

( ̄▽ ̄)"

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std; const int eps=1e-7;
const int MAXN=110;
int N,M,S;
double V,Vcur[MAXN],R[MAXN][MAXN],C[MAXN][MAXN];
bool vis[MAXN];
int cntNode[MAXN]; bool SPFA()
{
queue<int> que;
int u,v; for(int i=1;i<=N;i++)
Vcur[i]=0,vis[i]=0,cntNode[i]=0;
Vcur[S]=V;vis[S]=1;cntNode[S]=1;
que.push(S); while(!que.empty())
{
u=que.front();que.pop();
vis[u]=0; for(v=1;v<=N;v++)
{
if((Vcur[u]-C[u][v])*R[u][v]>Vcur[v]+eps)
{
Vcur[v]=(Vcur[u]-C[u][v])*R[u][v];
if(!vis[v])
{
vis[v]=1;
++cntNode[v];
que.push(v);
if(cntNode[v]>N)
return true;
}
}
}
}
return false;
} int main()
{
scanf("%d%d%d%lf",&N,&M,&S,&V);
int a,b;
double r,c,rr,cc;
while(M--)
{
scanf("%d%d%lf%lf%lf%lf",&a,&b,&r,&c,&rr,&cc);
R[a][b]=r;C[a][b]=c;
R[b][a]=rr;C[b][a]=cc;
}
if(!SPFA()) printf("NO\n");
else printf("YES\n");
return 0;
}
上一篇:HDU 5619 Jam's store


下一篇:在Android Studio上测试运行,Unity发布成Android包过程中所遇到的问题及解决方案