Mr. Panda and God Sheep are roommates and working in the same company. They always take subway to work together. There are NN subway stations on their route, numbered from 1 to NN . Station 1 is their home and station NN is the company.
One day, Mr. Panda was getting up later. When he came to the station, God Sheep has departed XX minutes ago. Mr. Panda was very hurried, so he started to chat with God Sheep to communicate their positions. The content is when Mr. Panda is between station AA and BB , God Sheep is just between station CC and DD .
BB is equal to A+1A+1 which means Mr. Panda is between station AA and A+1A+1 exclusive, or BB is equal to AA which means Mr. Panda is exactly on station AA . Vice versa for CC and DD . What’s more, the communication can only be made no earlier than Mr. Panda departed and no later than God Sheep arrived.
After arriving at the company, Mr. Panda want to know how many minutes between each adjacent subway stations. Please note that the stop time at each station was ignored.
Input
The first line of the input gives the number of test cases, TT . TT test cases follow.
Each test case starts with a line consists of 3 integers NN , MM and XX , indicating the number of stations, the number of chat contents and the minute interval between Mr. Panda and God Sheep. Then MM lines follow, each consists of 4 integers AA , BB , CC , DD , indicating each chat content.
1≤T≤301≤T≤30
1≤N,M≤20001≤N,M≤2000
1≤X≤1091≤X≤109
1≤A,B,C,D≤N1≤A,B,C,D≤N
A≤B≤A+1A≤B≤A+1
C≤D≤C+1C≤D≤C+1
Output
For each test case, output one line containing “Case #x: y”, where xx is the test case number (starting from 1) and yy is the minutes between stations in format t1,t2,...,tN−1t1,t2,...,tN−1 . titi represents the minutes between station ii and i+1i+1 . If there are multiple solutions, output a solution that meets 0<ti≤2×1090<ti≤2×109 . If there is no solution, output “IMPOSSIBLE” instead.
Sample Input
2
4 3 2
1 1 2 3
2 3 2 3
2 3 3 4
4 2 2
1 2 3 4
2 3 2 3Sample Output
Case #1: 1 3 1
Case #2: IMPOSSIBLE
Hint
In the second test case, when God Sheep passed the third station, Mr. Panda hadn’t arrived the second station.
They can not between the second station and the third station at the same time.题意：
1到n个站点，1为起点，n为终点，山羊比熊猫早出发x分钟，在m次交流中，每次熊猫在a和b站之间，山羊在c和d站之间，如果a==b说明在第a站（c==d同）。问从1到n中每相邻两站间需要的时间。
分析：
差分约束系统。
我们要求的是每两站之间用时最小值，建完图后求最长路。
PS（真丢人！！）：spfa如何跑最长路！！ ！
将所有不等式转化为x-y>=z的形式，每个不等式建一条 从y到x，权值为z 的边，spfa的时候dis初始化为极小值（0xc0c0c0c0 本菜鸡刚知道，纪念一下orz）
对于a b c d，可得：d-a>x 即d-a>=x+1
c-b<x 即b-c>-x 即b-c>=-x+1
如果a==b&&c==d：d-a=x 即d-a>=x且a-d>=-x
（差分约束通病）隐含条件！！ 因为已知每两站之间至少需用时1分钟，即i-(i-1)>=1
边建多了，数组开大点，亲测一遍TLE。
好了。可以快乐地spfa了~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e4+50;///下面有多余的边，开小了会超时。
const int inf=0xc0c0c0c0;///这是int。
ll dis[N],vis[N],head[N],num[N];
ll n,m,tot,x;
struct Edge
{
ll u,v,w,next;
} edge[N];
void add(ll a,ll b,ll c)
{
edge[tot].u=a;
edge[tot].v=b;
edge[tot].w=c;
edge[tot].next=head[a];
head[a]=tot++;
}
bool spfa(ll s)
{
queue<ll>q;
for(ll i=0; i<=n+1; i++)
dis[i]=inf;
memset(vis,false,sizeof(vis));
memset(num,0,sizeof(num));
q.push(s);
dis[s]=0;
while(!q.empty())
{
ll pos=q.front();
q.pop();
vis[pos]=false;
num[pos]++;
for(ll i=head[pos]; i!=-1; i=edge[i].next)
{
if(dis[edge[i].v] < dis[edge[i].u]+edge[i].w)
{
dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
if(!vis[edge[i].v])
{
vis[edge[i].v]=true;
q.push(edge[i].v);
if(num[edge[i].v]>=n)
return false;
}
}
}
}
return true;
}
int main()
{
int t,kcase=0;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&n,&m,&x);
ll a,b,c,d;
tot=0;
memset(head,-1,sizeof(head));
memset(edge,0,sizeof(edge));
for(int i=2; i<=n; i++)
add(i-1,i,1);
while(m--)
{
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
int f=0;
if(a!=b||c!=d)
f=1;
add(c,b,-x+f);///见分析。
add(a,d,x+f);
}
bool flag=spfa(1);
if(flag&&dis[n]==inf)
flag=0;
cout<<"Case #"<<++kcase<<": ";
if(!flag)
cout<<"IMPOSSIBLE"<<'\n';
else
{
for(int i=2; i<=n; i++)
{
cout<<dis[i]-dis[i-1];
if(i<n)
cout<<' ';
}
cout<<'\n';
}
}
return 0;
}
京公网安备 11010502036488号