Poj 3169 Layout

梦里梦外; 2022-05-07 00:28 78阅读 0赞

## 题目：[点击打开链接][Link 1]   题意：一共有n头牛，有ml个关系好的牛的信息，有md个关系不好的牛的信息，对应输入的第一行的三个元素，接下来ml行，每行三个元素A,B,D，表示A牛和B牛相距不希望超过D，接下来md行，每行三个元素A,B,D表示A牛和B牛的相距至少要有D才行。求1号牛和n号牛的最大距离，如果距离无限大输出-2，如果无解输出-1。   分析：差分约束入门题，差分约束的本质是差分+约束条件，可以转化为图论的最短路模型，入门参考[https://blog.csdn.net/mengxiang000000/article/details/52613328][https_blog.csdn.net_mengxiang000000_article_details_52613328]、[https://www.cnblogs.com/Renyi-Fan/p/7507899.html][https_www.cnblogs.com_Renyi-Fan_p_7507899.html]。 ##

## 补充：开始把距离数组设成long long（其实不需要开LL），用memset函数初始化为0x3f3f3f3f一直报错，改成int就对了，原来memset函数初始化之后的值不是0x3f3f3f3f了，而是0x3f3f3f3f3f3f3f3f，因为是按字节赋值，将LL8个字节全部变成了00111111。 ##

## 代码： ##

#pragma comment(linker, "/STACK:102400000,102400000")
    ///#include<unordered_map>
    ///#include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    const ll mod = 1e9+7;
    const int N = 1e4+10;
    
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    int n,ml,md,tot,hd[10000],vs[10000],ct[10000];
    int d[10000];
    
    struct eg{
        int to,w,nt;
    }e[200000];
    
    void init() {
        mst(hd,-1);
        tot=0;
    }
    
    void add(int u,int v,int w) {
        e[tot].to=v;
        e[tot].w=w;
        e[tot].nt=hd[u];
        hd[u]=tot++;
    }
    
    void spfa() {
        mst(vs,0);
        mst(ct,0);
        mst(d,inf);
        d[1]=0;
        int fg=0;
        queue<int> q;
        q.push(1);
        while(!q.empty()) {
            int u=q.front(); q.pop();
            vs[u]=0;
            if(++ct[u]>n) {
                fg=1;break;
            }
            for(int i=hd[u];i!=-1;i=e[i].nt) {
                int v=e[i].to;
                if(d[u]+e[i].w<d[v]) {
                    d[v]=d[u]+e[i].w;
                    if(!vs[v]) vs[v]=1,q.push(v);
                }
            }
        }
        if(fg) printf("-1\n");
        else if(d[n]==inf) printf("-2\n");
        else printf("%d\n",d[n]);
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        while(~scanf("%d%d%d",&n,&ml,&md)) {
            init();
            int a,b,c;
            for(int i=1;i<=ml;i++) {
                scanf("%d%d%d",&a,&b,&c);
                add(a,b,c);
            }
            for(int i=1;i<=md;i++) {
                scanf("%d%d%d",&a,&b,&c);
                add(b,a,-c);
            }
            spfa();
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=3169
[https_blog.csdn.net_mengxiang000000_article_details_52613328]: https://blog.csdn.net/mengxiang000000/article/details/52613328
[https_www.cnblogs.com_Renyi-Fan_p_7507899.html]: https://www.cnblogs.com/Renyi-Fan/p/7507899.html