第一次做差分约束的题，和zzy神牛一起做的，今天的目标还是3题，这是第一题。
差分约束就是有N个点M个约束条件，去寻找所需要的东西。可以用SPFA也可以用BellmanFord，但是这个题的问题在于没有原点，于是乎~
1.>建立一个超级原点，该原点到所有的店的距离都是0，将所有点都入队，再通过SPFA去寻找最短路径。如果说从超级原点到任何点的距离变成了负数，也就是说存在一个负环，这样便会进入死循环。输出无解。
2.>将所有点都入队，标记。当队首元素为INF时，将其修改为0，作为原点。这样可以存在多个原点。最后，使用一个cnt数组来标记每个点入队的次数，若大于N-1即顶点数-1，则出现死循环，输出无解。
另外构图呢~~~
i->j=p i点到j的值为p.放置在图中也就是
i->j>=p;i->j<=p;
dist[j]<=dist[i]+p;dist[j]>=dist[i]+p;
=>dist[j]<=dist[i]+p;
dist[i]<=dist[j]-p;
也就是i->j有为p的路径 j->i有为-p的路径。
这样构图就ok了~ 然后就开始裸了
#include<iostream>
#include<queue>
#define MAXN 1001
#define MAXM 100001
#define INF 0x7F7F7F7F
using namespace std;struct node
{int v;int price;node *next;
}edge[2][MAXM],*ptr[MAXN];int dist[MAXN];
int N,M;bool spfa()
{bool used[MAXN];int cnt[MAXN];memset( dist,0x7F,sizeof(dist) );memset( used,1,sizeof(used) );memset( cnt,0,sizeof(cnt) );int i,j,k;queue<int>myQueue;while( !myQueue.empty() )myQueue.pop();for( i=1;i<=N;i++ )myQueue.push(i);int u;while( !myQueue.empty() ){u=myQueue.front();myQueue.pop();if( dist[u]==INF ) dist[u]=0;node *p=ptr[u];used[u]=false;while( p ){if( dist[p->v]>dist[u]+p->price ){ dist[p->v]=dist[u]+p->price;if( !used[p->v] ){myQueue.push(p->v);used[p->v]=true;if( ++cnt[u]>N-1 ) return false;}}p=p->next;}}return true;
}int main()
{char com;int i,j,k;while( scanf("%d %d",&N,&M )!=EOF ){int u,v,val;for( i=1;i<=N;i++ ) ptr[i]=NULL;for( i=1;i<=M;i++ ){scanf( "\n%c %d %d",&com,&u,&v );if( com=='P' ){scanf( "%d",&val );node *p=&edge[0][i];p->v=v;p->price=val;p->next=ptr[u];ptr[u]=p;p=&edge[1][i];p->v=u;p->price=-val;p->next=ptr[v];ptr[v]=p;}else{node *p=&edge[0][i];p->v=u;p->price=-1;p->next=ptr[v];ptr[v]=p;}}if( spfa() )printf( "Reliable\n" );elseprintf( "Unreliable\n" );}return 0;
}