思路:
假设i<=j:
两只奶牛可以站在同一个位置,但是必须升序排列,所以有差分约束方程D[i] - D[i+1] <= 0;
对于两只有好感的奶牛有差分约束方程D[j] -D[i ]<= k;
对于两只反感的奶牛有差分约束方程D[i] - D[j] <= - k;
有了约束方程就可以spfa;
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX=0x3f3f3f3f,mx=1010;
int n,ml,md,bb,h[mx],vis[mx],dis[mx],cen[mx];
struct{int u,v,w,next;
}edg[mx*mx];
void add(int u,int v,int w){//edg[bb].u=u;edg[bb].v=v;edg[bb].w=w;edg[bb].next=h[u];h[u]=bb++;
}
int spfa(){memset(vis,0,sizeof(vis));memset(dis,MAX,sizeof(dis));memset(cen,0,sizeof(cen));queue<int>q;q.push(1);dis[1]=0;while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=h[x];i!=-1;i=edg[i].next){int v=edg[i].v;if(dis[v]>dis[x]+edg[i].w){dis[v]=dis[x]+edg[i].w;if(!vis[v]){vis[v]=1;q.push(v);if(++cen[v]>n) return -1;}}}}return 0;
}
int main(){while(scanf("%d%d%d",&n,&ml,&md)!=EOF){bb=0;memset(h,-1,sizeof(h));int a,b,c;for(int i=0;i<ml;i++){scanf("%d%d%d",&a,&b,&c);if(a>b) swap(a,b);add(a,b,c);}for(int i=0;i<md;i++){scanf("%d%d%d",&a,&b,&c);if(a<b) swap(a,b);add(a,b,-c);}if(spfa()==-1) puts("-1");else if(dis[n]==MAX) puts("-2");else printf("%d\n",dis[n]);// cout<<n<<endl;}return 0;
}