题目链接：

【题目大意】

货币转换问题，给你初始金额还有货币种类。然后给你货币之间的汇率及手续费（转换时额外的花销）。问能否通过货币间的转换实现自己的本金增大。

将dis 数组初始化为0

用 SPFA不断 的进行松弛操作， 发现当前金额可以比本身大， 就更新，同时记录更新次数。如果更新次数超过n次，说明存在”正“环。

这里先说明下负环。（求最短距离的时候）

在我们用SPFA求最短路径的时候，如果存在负环，在松弛操作的时候总会加入队列 因为最小距离会越来越小，同样这里如果经过一次次的转换，如果可以使本金增大，那么松弛操作也会无限进行下去，我们以n为界限，超过n就说明存在正环，也就说明可以使本金增大。

【源代码】

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int V = 3000;const int E = 1500;const double INF = 10000000.0;struct node{	int v,next;	double R,C;}pnt[E];int head[V];double dis[V]; // no ideabool vis[V];int cnt[V];int e = 0;int N,M;int src;double val;void addedge(int u,int v,double R, double C){	pnt[e].v = v; 	pnt[e].R = R; pnt[e].C = C;	pnt[e].next = head[u];	head[u] = e++;}void init(){    e=0;    memset(head, -1,sizeof(head));    memset(vis, 0 ,sizeof(vis));    memset(cnt, 0 ,sizeof(cnt));    for(int i=0; i<=N; i++) dis[i] = 0;}int SPFA(){	queue
        
         Q;	Q.push(src) ; vis[src] = 1;dis[src] = val; ++cnt[src];	while(!Q.empty()){		int u = Q.front(); Q.pop(); vis[u] = 0;		for(int i=head[u] ; i!=-1 ; i=pnt[i].next){			int v = pnt[i].v;			double tmp =  (dis[u]-pnt[i].C)*pnt[i].R; //当前位置可能变成的值			             //本金 减去利息 再乘汇率；			if(dis[v] 
         
           N) return -1; //negative cycle //如果一个点能变大N次以上 。 说明他还能继续增大，说明原值已经可以通过转换增大 } } } return 1;} int main(){ scanf("%d%d",&N,&M); scanf("%d",&src); scanf("%lf",&val); init(); int a,b; double Rab,Rba,Cab,Cba; for(int i=0;i