题目大意：

　　一条直线上有n个点，两个人在直线上走，保持x的距离。

　　告诉你m条信息，告诉你一个人在ab之间时，另一个人在cd之间。

　　问这些信息是否矛盾，如果不矛盾，求相邻两点之间的最小距离。

思路：

　　m条信息相当于告诉你两个点对之间距离与x的关系。

　　在点对之间连一条x的边，（注意判断刚好在某一个点的情况，讨论清楚是x还是x-1）。

　　然后直接SPFA即可。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 inline int getint() { 6     register char ch; 7     while(!isdigit(ch=getchar())); 8     register int x=ch^'0'; 9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');10     return x;11 }12 const int N=2001;13 int n,m,x;14 struct Edge {15     int to,w;16 };17 bool inq[N];18 std::queue
         
           q;19 int dis[N],cnt[N];20 std::vector
          
            e[N];21 inline void add_edge(const int &u,const int &v,const int &w) {22 e[u].push_back((Edge){v,w});23 }24 inline void reset() {25 while(!q.empty()) q.pop();26 for(register int i=0;i<=n;i++) {27 dis[i]=cnt[i]=inq[i]=0;28 e[i].clear();29 }30 }31 int main() {32 const int T=getint();33 for(register int i=1;i<=T;i++) {34 printf("Case #%d: ",i);35 n=getint(),m=getint(),x=getint();36 for(register int i=0;i
           
            n) {51 puts("IMPOSSIBLE");52 goto Next;53 }54 for(unsigned i=0;i
            
             dis[y]) {57 dis[y]=dis[x]+w;58 if(!inq[y]) {59 q.push(y);60 inq[y]=true;61 }62 }63 }64 }65 for(register int i=2;i<=n;i++) {66 printf("%d%c",dis[i]-dis[i-1]," \n"[i==n]);67 }68 Next:69 reset();70 }71 return 0;72 }