HDU6254 Subway Chasing

https://vjudge.net/contest/400914#problem/J
差分约束系统，设$T_i$是到达$i$站的时刻，则$T_i-T_{i-1}>=1$
对于每个条件，若$a==b\&\&c==d$，则$T_d-T_b==1$，否则$T_d-T_a>X\&\&T_c-Tb<X$
据此建图，再加一个超级源，连到每个点，边权为0，使图连通，跑一遍spfa，若有负环，则失败，否则可行。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+100;
const int INF=0x3f3f3f3f;

int T,n,m,x;
int d[maxn],inq[maxn],cnt[maxn];
struct Edge{
    int to,dist;
};
vector<Edge> edges;
vector<int> G[maxn];

bool SPFA(int s)
{
    queue<int>Q;
    memset(inq,0,sizeof(inq));
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++)d[i]=INF;
    d[s]=0;
    inq[s]=1;
    Q.push(s);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        inq[u]=false;
        for(int i=0;i<G[u].size();i++)
        {
            Edge& e=edges[G[u][i]];
            if(d[u]<INF && d[e.to]>d[u]+e.dist)
            {
                d[e.to]=d[u]+e.dist;
                if(!inq[e.to])
                {
                    Q.push(e.to);
                    inq[e.to]=1;
                    if(++cnt[e.to]>n)return false;
                }
            }
        }
    }
    return true;
}

void AddEdge(int a,int b,int c)
{
    edges.push_back((Edge){b,c});
    G[a].push_back(edges.size()-1);
}

int main()
{
	//freopen("input.in","r",stdin);
    cin>>T;
    for(int kase=1;kase<=T;kase++)
    {
        cin>>n>>m>>x;
        edges.clear();
        for(int i=1;i<=n;i++)G[i].clear();
		for(int i=1;i<=n;i++)AddEdge(0,i,0);
        for(int i=2;i<=n;i++)AddEdge(i,i-1,-1);
        for(int i=1;i<=m;i++)
        {
            int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
            if(a==b&&c==d)AddEdge(c,a,-x),AddEdge(a,c,x);
            else AddEdge(d,a,-x-1),AddEdge(b,c,x-1);
        }
        if(!SPFA(0))printf("Case #%d: IMPOSSIBLE\n",kase);
        else
        {
            printf("Case #%d:",kase);
            for(int i=2;i<=n;i++)printf(" %d",d[i]-d[i-1]);
            putchar('\n');
        }
    }
    return 0;
}