http://poj.org/problem?id=2983
题意：N 个 defense
stations，M条消息，消息有精确和模糊之分，若前边为P。则为精确消息，有两个defense
stations和他们之间的距离，若为P A B X 则是精确消息，并且A在B北边X光年远，V
A B则是模糊消息，A在B北边，不知道距离，但至少是1光年远。
思路 ：这个题要转化成差分约束。因为dist[a]-dist[b] = x,所以转化成差分约束x<=dist[a]-dist[b]<=x ,模糊消息因为至少为1，所以转化后为 dist[b] - dist[a] >= 1,化简之后为 dist[b] - dist[a] <= x dist[a] - dist[b] <= -x dist[a] - dist[b] <= -1.
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> using namespace std ; const int INF = 99999999 ; int cnt,m ,n; int dist[15010] ;//源点到各点的距离 struct node { int u,v,w ; }edge[10700700] ; void addedge(int u,int v,int w)//加边 { edge[cnt].u = u ; edge[cnt].v = v ; edge[cnt].w = w ; cnt++ ; } bool bellman_ford(int start) { for(int i = 1 ; i <= n ; i++) i == start ? dist[i] = 0 : dist[i] = INF ; for(int i = 1 ; i < n ; i++) { bool flag = false ; for(int j = 0 ; j < cnt ; j++) { int u = edge[j].u,v = edge[j].v,w = edge[j].w ; if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w ; flag = true ; } } if(!flag)//若dist没有任何改变说明以后也不会变，可直接返回 return true ; } for(int j = 0 ; j < cnt ; j++) { int u = edge[j].u,v = edge[j].v,w = edge[j].w ; if(dist[v] > dist[u] + w) return false ; } return true ; } int main() { char ch ; int u,v,w ; while(~scanf("%d %d",&n,&m)) { cnt = 0 ; for(int i = 0 ; i < m ; i++) { getchar() ; scanf("%c",&ch) ; if(ch == ‘P‘) { scanf("%d %d %d",&u,&v ,&w) ;//两点距离确定建立双向边 addedge(v,u,-w) ; addedge(u,v,w) ; } if(ch == ‘V‘) { scanf("%d %d",&u,&v) ;//两点距离不定，建立单向边 addedge(v,u,-1) ; } } if(bellman_ford(1)) printf("Reliable\n") ; else printf("Unreliable\n") ; } return 0 ; }