「NOIP模拟赛」排队
「问题描述」
Czy喜欢将他的妹子们排成一队。假设他拥有N只妹纸，编号为1至N。Czy让他们站成一行，等待自己来派送营养餐。这些妹纸按照编号大小排列，并且由于它们都很想早点吃饭，于是就很可能出现多只妹纸挤在同一位置的情况(也就是说，如果我们认为妹纸位于数轴上，那么多只妹纸的位置坐标可能相同)。
因为众所周知的原因，某些妹纸之间互相喜欢，他们希望互相之间的距离至多为一个定值。但某些妹纸之间互相厌恶，他们希望互相之间的距离至少为一个定值。现在给定ML个互相喜爱的妹纸对以及他们之间距离的最大值，MD个互相厌恶的妹纸对以及他们之间距离的最小值。
你的任务是计算在满足以上条件的前提下，帮助Czy计算出编号为1和编号为N的妹纸之间距离的最大可能值。
「输入」
输入文件为 layout.in。
第一行有 3 个整数，每两个整数之间用一个空格隔开，依次表示 n,ML和DL ；
此后ML行，每行包含三个用空格分开的整数A,B和D，其中A,B满足1<=A<=B<=N。表示编号为A和B的妹纸之间的距离至多为D。
此后MD行，每行包含三个用空格分开的整数A,B和D，其中A,B满足1<=A<=B<=N。表示编号为A和B的妹纸之间的距离至少为D。
「输出」
输出文件名为 layout.out。
输出文件仅包含一个整数。如果不存在任何合法的排队方式，就输出-1。如果编号1和编号N的妹纸间距离可以任意，就输出-2 。否则输出他们之间的最大可能距离。
「输入输出样例」
|
layout.in |
layout.out |
|
4 2 1 1 3 10 2 4 20 2 3 3 |
27 |
「数据范围」
对于40%的数据，N<=100；
对于100%的数据，N<=1000；ML,MN<=10000；D<=1000000。
题解
很明显可以看出是差分约束系统的题目，如果A和B距离至多为D则建边A->B权值为D，距离至少为D则建边B->A权值为-D。然后最短路。若有负权环则输出-1，若无法到达点N则输出-2，否则直接输出1~N的距离即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define pa pair<int,int> #define inf (1LL<<60) #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ml,md,cnt; int t[1005],last[1005],fa[1005],q[1005]; ll dis[1005]; bool inq[1005]; struct data{int to,next,v;}e[40005]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; } int spfa() { for(int i=1;i<=n;i++)dis[i]=inf; int head=0,tail=1; q[0]=1;t[1]++;dis[1]=0; while(head!=tail) { int now=q[head];inq[now]=0;head++; if(head==1002)head=0; for(int i=last[now];i;i=e[i].next) if(dis[now]+e[i].v<dis[e[i].to]) { t[e[i].to]++; if(t[e[i].to]==n+1)return 0; dis[e[i].to]=dis[now]+e[i].v; if(!inq[e[i].to]) { inq[e[i].to]=1; q[tail++]=e[i].to; if(tail==1002)tail=0; } } } return 1; } int main() { //freopen("layout.in","r",stdin); //freopen("layout.out","w",stdout); n=read();ml=read();md=read(); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=ml;i++) { int a=read(),b=read(),d=read();d=abs(d); insert(a,b,d); } for(int i=1;i<=md;i++) { int a=read(),b=read(),d=read();d=abs(d); insert(b,a,-d); } if(!spfa())puts("-1"); else if(dis[n]==inf)puts("-2"); else printf("%I64d\n",dis[n]); return 0; } |
OI 课件=>
