Submission #6904276

---

Source Code Expand

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define endl '\n'
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ull unsigned long long
#define int long long
#define iter set<int>::iterator
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=2e5+7;
const int inf=1e18+5;
const int mod=2520;

int n,m,p;
vector< pair< pair<int,int>,int > >q;
vector< pair< pair<int,int>,int > >qq;
int d[N];
int d1[N];
int d2[N];

main ()
{
    ios;
    cin>>n>>m>>p;
    for (int i=1;i<=m;++i){
        int x,y,z;
        cin>>x>>y>>z;
        z-=p;
        z=-z;
        q.pb({{x,y},z});
        qq.pb({{y,x},z});
    }
    for (int i=1;i<=n-1;++i){
        d1[i]=inf;
    }
    for (int i=1;i<=n;++i){
        for (int j=0;j<qq.size();++j){
            int x=qq[j].ff.ff;
            if (d1[x]==inf)continue;
            int y=qq[j].ff.ss;
            int cost=qq[j].ss;
            if (d1[x]+cost<d1[y]){
                d1[y]=d1[x]+cost;
            }
        }
    }
    for (int i=2;i<=n;++i){
        d[i]=inf;
    }
    for (int i=1;i<=n;++i){
        for (int j=0;j<q.size();++j){
            int x=q[j].ff.ff;
            if (d[x]==inf)continue;
            int y=q[j].ff.ss;
            int cost=q[j].ss;
            if (d[x]+cost<d[y]){
                d[y]=d[x]+cost;
            }
        }
    }
    for (int i=1;i<=n;++i){
        d2[i]=d[i];
    }
    for (int i=1;i<=2*n;++i){
        for (int j=0;j<q.size();++j){
            int x=q[j].ff.ff;
            if (d[x]==inf)continue;
            int y=q[j].ff.ss;
            int cost=q[j].ss;
            if (d[x]+cost<d[y]){
                d[y]=d[x]+cost;
            }
        }
    }
    bool t=false;
    for (int i=1;i<=n;++i){
        if (d[i]<d2[i] && d1[i]!=inf){
            t=true;
            break;
        }
    }
    if (t || d[n]==inf){
        cout<<-1<<endl;
    }
    else {
        if (d[n]<0){
            cout<<-d[n]<<endl;
        }
        else {
            cout<<0<<endl;
        }
    }
}

Submission Info

Judge Result