【UOJ 710】排队

2024-02-22 23:06:40

【题目描述】：

Czy喜欢将他的妹子们排成一队。假设他拥有N只妹纸，编号为1至N。Czy让他们站成一行，等待自己来派送营养餐。这些妹纸按照编号大小排列，并且由于它们都很想早点吃饭，于是就很可能出现多只妹纸挤在同一位置的情况(也就是说，如果我们认为妹纸位于数轴上，那么多只妹纸的位置坐标可能相同)。

因为众所周知的原因，某些妹纸之间互相喜欢，他们希望互相之间的距离至多为一个定值。但某些妹纸之间互相厌恶，他们希望互相之间的距离至少为一个定值。现在给定ML个互相喜爱的妹纸对以及他们之间距离的最大值，MD个互相厌恶的妹纸对以及他们之间距离的最小值。

你的任务是计算在满足以上条件的前提下，帮助Czy计算出编号为1和编号为N的妹纸之间距离的最大可能值。

【输入描述】：

第一行有 3 个整数，每两个整数之间用一个空格隔开，依次表示 n,ML和MD；

此后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。

【输出描述】：

输出文件仅包含一个整数。如果不存在任何合法的排队方式，就输出-1。如果编号1和编号N的妹纸间距离可以任意，就输出-2 。否则输出他们之间的最大可能距离。

【样例输入】：

【样例输出】：

【时间限制、数据范围及描述】：

时间：1s 空间：128M

对于40%的数据，N<=100；

对于100%的数据，N<=1000；ML,MN<=10,000；D<=1,000,000。

题解：差分约束……我大意了没有闪数组开小惨70分！气死我了

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1002;
int x,y,z,n,ml,md;
struct node{
    int next;
    int to;
    int w;
}e[N*4]; 
int tot[N],cnt,head[N];
int dis[N];
int vis[N];
void add(int x,int y,int z){
    e[++cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt;
} 
queue<int>q; 
int spfa(int ss){
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    //for(int i=0;i<=N;i++) dis[i]=(ll)10000000000003;
    memset(tot,0,sizeof(tot));
    q.push(ss); vis[ss]=1; dis[ss]=0; 
    while(!q.empty()){
        int u=q.front(); vis[u]=0; q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){ vis[v]=1; q.push(v); tot[v]++; }
            }
            if(tot[v]>=n) return -1;
        }
    }
    if(dis[1]==0x3f3f3f3f) return -2;
    return dis[1];
}
int main(){
    freopen("layout.in","r",stdin);
    freopen("layout.out","w",stdout);
    scanf("%d %d %d",&n,&ml,&md);
    for(int i=1;i<=ml;i++){
        scanf("%d %d %d",&x,&y,&z);
        add(y,x,z);
    }
    for(int i=1;i<=md;i++){
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,-z); 
    }
    printf("%d",spfa(n));
//    if(dis[1]==0x3f3f3f3f) printf("-2");
//    else printf("%d\n",dis[1]);
    return 0;
}

码农公寓