最短路中，求出源到各点的最短路。如果a->b有一条边，那么dis[a]+w(a,b)>=dis[b].
将所有的条件转化成边即可。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=1010;
const int maxm=1000000;
const int INF=1000000000;
struct node
{
int t;
int w;
node *next;
}edge[maxm],*adj[maxn];
int len=0;
void init(int n)
{
for(int i=0;i<n;i++)
adj[i]=NULL;
len=0;
}
void addedge(int u,int v,int w)
{
edge[len].t=v;edge[len].w=w;edge[len].next=adj[u];adj[u]=&edge[len++];
}
int dis[maxn];//[0,n-1]
int use[maxn];
int cnt[maxn];
bool SPFA(int n,int s)
{
queue<int>Q;
fill(dis,dis+n,INF);
fill(use,use+n,0);
fill(cnt,cnt+n,0);
dis[s]=0;
use[s]=1;
Q.push(s);
while(!Q.empty())
{
int x=Q.front();Q.pop();
use[x]=0;
++cnt[x];
if(cnt[x]>n)return false;
for(node *p=adj[x];p;p=p->next)
{
int t=p->t,w=p->w;
if(dis[x]+w<dis[t])
{
dis[t]=dis[x]+w;
if(!use[t])
{
Q.push(t);
use[t]=1;
}
}
}
}
return true;
}
int main()
{
int ca;
scanf("%d",&ca);
while(ca--)
{
int n,x,y;
scanf("%d%d%d",&n,&x,&y);
init(n);
for(int i=0;i<x;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
a--;b--;
addedge(a,b,c);
}
for(int i=0;i<y;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
a--;b--;
addedge(b,a,-c);
}
//for(int i=0;i<n-1;i++)
// addedge(i+1,i,0);
if(!SPFA(n,0))printf("-1\n");
else if(dis[n-1]==INF)printf("-2\n");
else printf("%d\n",dis[n-1]);
}
return 0;
}