思路：
假设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; }