大致题意：给出一些点的精确信息和模糊信息，精确信息给出两点的位置和距离，模糊信息给出两点的位置，但距离大于等于一。试确定是否所有的信息满足条件。

这道题让我对差分约束系统有了进一步的认识。设dist[i]表示源点到i的距离，精确条件可以判断出两个差分条件：假如a->b为c则可以写成c>=dist[b]-dist[a]>=c；所以可得dist[b]<=dist[a]+c , dist[a]<=dist[b]-c；这就说明a到b有一条长度为c的边，b到a有一条长度为-c的边。模糊信息可以确定一个差分条件由dist[b]-dist[a]>=1可得：dist[a]<=dist[b]-1，说明b到a有一条长度为-1的边。差分条件都找出来后在求最短路看是否有负环。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define MAX_INT 123456789
struct node
{
	int v;
	int value;
	int next;
};
int visit[1001],head[1001],counter[1001],dist[1001],N;
node edge[1000000];
queue <int> Q;
int spfa(int n)
{
	int i,k,tail,front,e;
	while(!Q.empty()) Q.pop();
	for(tail=front=0,i=1;i<=n;i++)
	{
		dist[i]=MAX_INT;
		Q.push(i);
		visit[i]=1;
	}
	memset(counter,0,sizeof(counter));
	while(!Q.empty())
	{
		e=Q.front(),Q.pop();
		visit[e]=0;
		if(dist[e]==MAX_INT) dist[e]=0;
		for(i=head[e];i;i=edge[i].next)
		{
			k=edge[i].v;
			if(dist[k]>dist[e]+edge[i].value)
			{
				dist[k]=dist[e]+edge[i].value;
				if(!visit[k])
				{
					Q.push(k);
					visit[k]=1;
					if(++counter[k]>n-1) return 0;
				}
			}
		}
	}
	return 1;
}
int add(int s,int t,int w)
{
	node e={t,w,0};
	edge[N]=e;
	edge[N].next=head[s];
	head[s]=N++;
	return 0;
}
int main()
{
	int i,s,t,w,m,n;
	char c;
	freopen(\"in.txt\", \"r\", stdin);
    freopen(\"out.txt\",\"w\", stdout);
	while(cin>>n>>m)
	{
		memset(head,0,sizeof(head));
		for(N=1,i=0;i<m;i++)
		{
			cin>>c;
			if(c==\'P\')
			{
				cin>>s>>t>>w;
				add(s,t,w);
				add(t,s,-w);
			}
			else if(c==\'V\')
			{
				cin>>s>>t;
				add(t,s,-1);
			}
			getchar();
		}
		if(spfa(n))
			cout<<\"Reliable\"<<endl;
		else
			cout<<\"Unreliable\"<<endl;
	}
	return 0;
}

附上几组测试数据：

input:

12 18
P 5 6 -4
P 11 9 5
V 4 2
V 8 3
V 1 4
P 3 10 -22
V 9 3
V 12 7
V 7 10
P 12 8 -25
V 4 3
V 10 9
V 8 6
P 12 9 22
V 8 12
V 2 11
P 12 3 -12
P 5 3 -4

27 16
P 7 17 -20
V 13 12
V 15 1
P 19 15 -16
V 11 16
V 3 11
V 20 27
P 7 18 3
V 13 25
P 19 12 -23
V 18 6
P 7 25 17
V 16 11
P 9 7 5
V 23 9
P 27 17 -21

17 11
V 17 5
V 5 14
V 14 3
V 12 1
V 8 14
P 1 9 -3
P 3 12 -5
V 17 2
P 7 5 -21
P 7 16 -14
P 1 13 -9

5 2
P 4 5 -18
P 4 3 -17

14 19
V 14 14
P 10 8 4
P 8 8 20
V 1 7
V 9 5
P 4 10 2
V 14 8
V 6 13
V 1 1
P 11 1 -26
V 4 9
V 12 5
P 3 1 8
P 6 7 11
P 5 4 -2
P 8 1 -26
P 4 14 -19
P 3 14 -18
V 12 2

18 7
P 18 18 -2
P 16 14 -11
V 16 10
V 17 2
P 8 17 16
V 5 9
V 13 18

30 27
V 29 13
V 26 15
V 2 3
V 1 29
V 30 4
V 17 8
V 20 8
P 20 14 5
P 27 26 -8
V 25 25
V 27 2
P 24 24 25
V 13 9
P 6 24 6
P 7 23 -1
P 3 20 1
P 14 27 14
P 10 4 -14
P 6 10 16
P 3 9 8
V 19 12
P 26 18 -4
P 25 15 12
V 21 18
V 19 18
V 21 24
P 3 6 -12

24 8
P 20 24 15
P 8 21 11
V 1 10
V 22 24
P 23 15 -26
P 12 9 -3
P 11 20 23
P 9 12 -25

21 15
V 16 6
V 12 2
P 11 5 -26
V 17 12
P 10 15 -22
V 2 16
P 12 20 -5
V 11 16
P 7 8 16
V 10 6
V 8 2
P 14 3 -2
V 6 21
V 11 18
P 8 8 -16

17 2
V 3 14
V 16 7

15 9
V 6 2
P 15 1 -13
P 11 3 -17
P 5 9 10
P 13 9 23
V 6 1
P 4 10 -25
V 10 11
P 13 11 13

7 27
P 6 1 7
V 7 4
P 3 1 2
P 1 4 3
V 2 1
P 2 1 -23
P 6 5 22
V 7 3
V 6 2
V 2 1
V 3 5
P 4 2 1
V 4 2
P 3 1 25
P 4 6 21
P 7 5 6
P 2 5 18
P 1 3 25
P 4 4 -7
P 3 6 6
P 4 1 -2
P 3 2 2
V 4 7
P 7 2 27
P 5 6 24
P 2 3 5
P 4 2 1

20 16
P 13 18 -29
V 8 8
V 10 1
V 15 2
V 16 4
V 13 5
V 13 20
P 9 8 4
P 19 11 17
P 4 2 -13
V 11 12
V 1 5
P 20 14 -1
P 13 11 5
V 4 3
P 8 5 28

15 24
V 6 3
P 4 15 22
V 15 15
V 1 11
P 14 1 1
P 8 3 -7
V 7 4
V 3 6
V 6 1
P 4 13 18
V 15 4
V 2 14
P 9 6 -11
P 9 2 0
V 11 1
P 8 7 23
P 6 4 13
P 14 4 29
P 10 1 -8
V 11 1
V 5 2
P 6 10 2
V 3 12
P 8 12 26

10 5
V 7 3
V 4 6
P 7 2 -4
P 3 7 -28
V 6 2

21 22
V 17 4
P 14 13 -22
V 1 18
P 2 18 -3
V 3 12
P 2 16 17
V 5 11
P 4 17 20
V 19 18
P 13 9 22
V 1 2
V 15 16
P 15 10 -19
V 4 3
V 16 1