World Exhibition

1
4 2 1
1 3 8
2 4 15
2 3 4

19

/* ***********************************************
Author        :CKboss
Created Time  :2015年07月30日 星期四 08时16分29秒
File Name     :HDOJ3592.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int maxn=1111;
const int INF=0x3f3f3f3f;

struct Edge
{
	int to,next,cost;
}edge[30300];

int Adj[maxn],Size;

void init()
{
	memset(Adj,-1,sizeof(Adj)); Size=0;
}

void Add_Edge(int u,int v,int c)
{
	edge[Size].to=v;
	edge[Size].cost=c;
	edge[Size].next=Adj[u];
	Adj[u]=Size++;
}

int n,m1,m2;

int dist[maxn],cq[maxn];
bool inq[maxn];

bool spfa(int rt)
{
	memset(dist,63,sizeof(dist));
	memset(cq,0,sizeof(cq));
	memset(inq,false,sizeof(inq));

	dist[rt]=0;
	queue<int> q;
	inq[rt]=true; q.push(rt); cq[rt]=1;

	while(!q.empty())
	{
		int u=q.front(); q.pop();

		for(int i=Adj[u];~i;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].cost)
			{
				dist[v]=dist[u]+edge[i].cost;
				if(!inq[v])
				{
					inq[v]=true;
					cq[v]++;
					if(cq[v]>=n) return false;
					q.push(v);
				}
			}
		}
		inq[u]=false;
	}
	return true;
}

int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	int T_T;
	scanf("%d",&T_T);
	while(T_T--)
	{
		scanf("%d%d%d",&n,&m1,&m2);
		init();
		int u,v,c;
		for(int i=0;i<m1;i++)
		{
			scanf("%d%d%d",&u,&v,&c);
			Add_Edge(u,v,c);
		}
		for(int i=0;i<m2;i++)
		{
			scanf("%d%d%d",&u,&v,&c);
			Add_Edge(v,u,-c);
		}

		bool fg=spfa(1);
		if(fg==false) puts("-1");
		else if(dist[n]==INF) puts("-2");
		else printf("%d\n",dist[n]);
	}
    
    return 0;
}

HDOJ 3592 World Exhibition 差分约束

原文：http://blog.csdn.net/ck_boss/article/details/47143935