POJ3169差分限制(SPFA+差分限制)

思路：

假設i<=j:

兩隻奶牛可以站在同一個位置，但是必須升序排列，是以有差分限制方程D[i] - D[i+1] <= 0；

對于兩隻有好感的奶牛有差分限制方程D[j] -D[i ]<= k；

對于兩隻反感的奶牛有差分限制方程D[i] - D[j] <= - k；

#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;
}