제출 #1268454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268454		amn	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	246 ms	25076 KiB

commuter_pass

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<tuple>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fastio() ios::sync_with_stdio(false);cin.tie(nullptr);
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pll pair<ll,ll>
#define pb push_back
#define fi first
#define se second
#define ll long long
#define lld double
#define sz(a) (ll)(a.size())
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define endl '\n'
const long long LINF = 1e18;
const ll MOD = 1e9+7;  
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << '=';_print(x);cerr << endl;
#else
#define debug(x)
#endif
void _print(int x) { cerr << x; }
void _print(long long x) { cerr << x; }
void _print(double x) { cerr << x; }
void _print(char x) { cerr << x; }
void _print(const string &x) { cerr << x; }
void _print(bool x) { cerr << (x ? '1' : '0'); }
void _print(pair<ll,ll> p) { cerr << '{' ;_print(p.first);cerr<<' ';_print(p.second);cerr<<'}'; }
template <typename T>
void _print(const vector<T> &v)
{cerr << '[';for (const auto &i : v){_print(i);cerr << ' ';}cerr << ']';}
template <typename T>
void _print(const multiset<T> &s){cerr << '{';for (const auto &i : s){_print(i);cerr << ' ';}cerr << '}';}
template <typename T>
void _print(const set<T> &s){cerr << '{';for (const auto &i : s){_print(i);cerr << ' ';}cerr << '}';}
template <typename K, typename V>
void _print(const map<K, V> &m){cerr << '{'<<endl;for (const auto &p : m){cerr << '(';_print(p.first);cerr << ':';_print(p.second);cerr << ')';}cerr << endl<<'}';}
template <typename T1, typename T2>
void _print(const pair<T1, T2> &p){cerr << '(';_print(p.first);cerr << ',';_print(p.second);cerr << ')';}
ll mod_add(ll&a,ll&b,ll m) {return (a+b)%m;}
ll mod_mul(ll&a,ll&b, ll m) {return (a*b)%m;}
ll mod_sub(ll&a,ll&b,ll m) {return ((a-b)%m+m)%m;}
ll gcd(ll a,ll b) {if(b==0) return a;return gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b/gcd(a,b);}
ll binExpo(ll a,ll n) {ll res=1;while(n) {if(n&1) {res=(res*a);}a=(a*a); n>>=1;}return res;}
ll N=3*1e5;
ll binExpom(ll a,ll n) {ll res=1;while(n) {if(n&1) {res=(res*a); res%=MOD;}a=(a*a); a%=MOD; n>>=1;}return res;}
ll modInv(ll a,ll mod) {return binExpom(a,mod-2);}
vector<ll>fact(N+2,0);
void calcFact() {fact[0]=1;fact[1]=1;for(ll i=2;i<=N;i++){fact[i]=mod_mul(fact[i-1],i,MOD);}}
ll ncr(ll n,ll r)
 {ll numr=fact[n];ll den=mod_mul(fact[n-r],fact[r],MOD);ll ans=(modInv(den,MOD)*numr)%MOD;return ans;}
vector<ll> sieve(ll N) {vector<ll>primes(N+1,1);primes[0]=primes[1]=0;for(int i=2;i*i<=N;i++) {for
(int j=i*i;j<=N;j+=i) {primes[j]=0;}}return primes;}
ll extEuclid(ll a,ll b,ll&x ,ll& y) {
if(b==0) {x=1;y=0;return a;}ll x1,y1;ll d=extEuclid(b,a%b,x1,y1);x=y1;y=x1-y1*(a/b);return d;}
vector<ll> findLps(string &s)
{vector<ll> lps(sz(s) + 1, 0);
ll len = 0;ll i = 1;ll n = sz(s);while (i < n){if (s[i] == s[len]){len++;lps[i] = len;i++;}else{if (len != 0){len = lps[len - 1];}else{len = 0;lps[i] = 0;i++;}}}return lps;}
vector<ll> calcZarray(string &s)
{ll n = sz(s);vector<ll> z(n + 1, 0);ll l = 0;ll r = 0;ll i = 1;while (i < n){
if (i < r){if (z[i - l] < r - l + 1){z[i] = z[i - l];}else{l = i;while (r < n and s[r] == s[r - l])r++;z[i] = r - l;r--;i++;}}else{l = i;r = i;while (r < n and s[r - l] == s[r]){r++;}z[i] = r - l;r--;i++;}}return z;}
vector<ll> segSieve(ll l, ll r, ll n){
vector<ll> prime = sieve(n);vector<ll> rangePrime(n + 1, 1);for (int i = 2; i * i <= r; i++){if (prime[i] == 1){int j = (l / i) * i;if (j < l){j += i;}j = max(i * i, j);for (int init = j - l; init < n; init += i){rangePrime[init] = 0;}}}return rangePrime;}
// /
void rabin_karp(string const& s, string const& t) {
auto f=[&](string str)-> ll{ll ht=0;for(int i=0;i<sz(str);i++) {ht=(ht*31 + str[i]-'a'+1)%MOD;}return ht;};ll h=0;ll n=sz(s);debug(n);vector<ll>ph(n+1,0);for(int i=0;i<n;i++) {ll dig=s[i]-'a'+1;h=(h*31LL+dig)%MOD;ph[i]=h;}ll cnt=0;ll ht=f(t);if(ph[sz(t)-1]==ht) cnt++;ll ws=sz(t);ll sub=binExpo(31,ws);for(int i=1;i<=n-ws;i++) {ll currH=ph[i+ws-1];currH=((currH-ph[i-1]*sub)%MOD + MOD)%MOD;if(currH==ht) cnt++;}}
/*<------------------------------------------------------------------------>*/
void binaryLifting(ll src,ll parent,vector<vector<ll>>&adj,vector<vector<ll>>&dp,vector<ll>&lvl,ll curr) {
    lvl[src]=curr;
    dp[src][0]=parent;
    debug(src)
    for(int i=1;i<=19;i++) {
        dp[src][i]=dp[dp[src][i-1]][i-1];
    }

    for(auto nbr:adj[src]) {
        if(nbr==parent) continue;

        binaryLifting(nbr,src,adj,dp,lvl,curr+1);

    }
}

vector<vector<ll>> buildSparseTable(ll n,vector<ll>&a) {
    vector<vector<ll>>st(20,vector<ll>(n+2,0));

    n=a.size();
    for(int i=0;i<n;i++) {
        st[0][i]=a[i];
    }
    for(int i=1;(1<<i)<=n;i++) {
        for(int j=0;j+(1<<i)<=n;j++) {
            st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
            // st[i][j]=gcd(st[i-1][j],st[i-1][j+(1<<(i-1))]);
        }
    }
    return st;

}
vector<ll> logTable(ll n) {
    vector<ll>lg(n+2,0);
    lg[1]=0;
    for(int i=2;i<=n;i++) {
        lg[i]=lg[i/2]+1;
    }
    return lg;
}
class SegTree {
private:
    vector<ll>seg;
    ll size;
public:
    SegTree(ll n) {
        // this->size=n;
        seg.resize(4*n+1,0);
    }
    void build(ll src,ll tl,ll tr,vector<ll>&a) {
        if(tl>tr) return;
        if(tl==tr) {
            seg[src]= a[tl];
            // seg[src]=vector<ll>(1,a[tl]);
            return;
        }
        ll tm=tl+(tr-tl)/2;
        build(2*src+1,tl,tm,a);
        build(2*src+2,tm+1,tr,a);
        seg[src]=(seg[2*src+1]+seg[2*src+2]);
        // seg[src]=max(seg[2*src+1],seg[2*src+2]);
        // merge(all(seg[2*src+1]),all(seg[2*src+2]),seg[src].begin());

    }
    void update(ll src,ll tl,ll tr,ll& pos,ll &val) {
        if(tl>tr) return;
        if(tl==tr) {
            seg[src]=val;
            return;
        }

        ll tm=tl+(tr-tl)/2;
        if(pos<=tm) {
            update(2*src+1,tl,tm,pos,val);
        }else {
            update(2*src+2,tm+1,tr,pos,val);
        }
        // seg[src]=max(seg[2*src+1],seg[2*src+2]);
        seg[src]=(seg[2*src+1]+seg[2*src+2]);
        // seg[src]=merge(seg[2*src+1],seg[2*src+2]);

    }
    ll findmn(ll src,ll tl,ll tr,ll k) {
        if(tl==tr) {
            return tl;
        }
        ll ans=1e6;
        ll tm=tl+(tr-tl)/2;
        if(seg[2*src+1]>=k) {
            ans=min(ans,findmn(2*src+1,tl,tm,k));
        }
        else if(seg[2*src+2]>=k) {
            ans=min(ans,findmn(2*src+2,tm+1,tr,k));
        }
        return ans;
    }
    ll findSum(ll src,ll tl,ll tr, ll l ,ll r) {
        if(l>r) {
            return 0;
        }
        if(tl==l and tr==r) return seg[src];
        ll tm=tl+(tr-tl)/2;
        return findSum(2*src+1,tl,tm,l,min(tm,r)) + findSum(2*src+2,tm+1,tr,max(tm+1,l),r);
    }

};

vector<ll> manacher(string ns){
    ll l=0;
    ll r=1;
    ll n=sz(ns);
    vector<ll>d(n,0);
    for(int i=1;i<=sz(ns)-2;i++) {
        d[i]=min(r-i,d[l+(r-i)]);
        while(ns[i-d[i]] == ns[i+d[i]]) d[i]++;
        if(i+d[i]>r) {
            l=i-d[i];
            r=i+d[i];
        }
    }
    return vector<ll>(begin(d)+1,end(d)-1);
}





/*
think of binary search
think in reverese direction
solve equation mathematically
try to merge two operation in one or split one operation in two
find optimal soln without using operation
*/
// d[0]=1;
// derangement  d(n)=(n-1)*(d(n-1)+d(n-2));
void solve() { 
    ll n,m,s,t,u,v;
    cin>>n>>m>>s>>t>>u>>v;
    vector<vector<pll>>adj(n+1);
    for(int i=1;i<=m;i++) {
        ll u1,v1,c;
        cin>>u1>>v1>>c;
        adj[u1].pb({v1,c});
        adj[v1].pb({u1,c});
    }

    vector<ll>d1(n+1,LINF);
    vector<ll>d2(n+1,LINF);
    // d1[s]=0;
    // d2[t]=0;
    auto dj=[&](ll src,vector<ll>&d) ->void {
        d[src]=0;
        priority_queue<pll,vector<pll>,greater<pll>>pq;
        pq.push({0,src});
        vector<ll>vis(n+1,0);
        while(!pq.empty()) {
            auto tp=pq.top();
            pq.pop();
            auto srcN=tp.second;
            auto srcC=tp.first;
            if(vis[srcN]) continue;
            vis[srcN]=1;
            for(auto nbr:adj[srcN]) {
                ll nbrN=nbr.first;
                ll nbrC=nbr.second;
                if(srcC+nbrC<d[nbrN]) {
                    d[nbrN]=srcC+nbrC;
                    pq.push({d[nbrN],nbrN});
                }
            }
        }
    };
    dj(u,d1);
    dj(v,d2);
    ll ans=min(d1[v],d2[u]);

    auto dj1=[&](ll src,ll dest,ll&ans) ->void {
        vector<ll>d(n+1,LINF);
        d[src]=0;
        priority_queue<pair<ll,pll>,vector<pair<ll,pll>>,greater<pair<ll,pll>>>pq;
        pq.push({0,{src,0}});
        vector<ll>vis(n+1,0);
        vector<vector<ll>>dp(2,vector<ll>(n+2,LINF));
        dp[0][src]=d1[src];
        dp[1][src]=d2[src];
        while(!pq.empty()) {
            auto tp=pq.top();
            pq.pop();
            auto srcN=tp.second.first;
            auto srcC=tp.first;
            ll par=tp.second.second;
            
            if(vis[srcN]) continue;
            vis[srcN]=1;
            for(auto nbr:adj[srcN]) {
                ll nbrN=nbr.first;
                ll nbrC=nbr.second;
                if(srcC+nbrC<d[nbrN]) {
                    d[nbrN]=srcC+nbrC;
                    dp[0][nbrN]=min({dp[0][srcN],d1[nbrN]});
                    dp[1][nbrN]=min({dp[1][srcN],d2[nbrN]});
                    pq.push({d[nbrN],{nbrN,srcN}});

                }
                if(srcC+nbrC==d[nbrN]) {
                    if(min(dp[0][srcN],d1[nbrN]) + min(dp[1][srcN],d2[nbrN]) <=dp[0][nbrN]+dp[1][nbrN] ) {
                        dp[0][nbrN]=min(dp[0][srcN],d1[nbrN]);
                        dp[1][nbrN]=min(dp[1][srcN],d2[nbrN]);
                    }
                }
            }
        } 
        ans=min(ans,dp[0][dest]+dp[1][dest]);   
    };

    dj1(s,t,ans);
    // dj1(t,s,ans);
    cout<<ans<<endl;
    // cout<<ans1+ans2<<endl;


        





        



}   
int main()

{
    // freopen("shortcut.in", "r", stdin);
    // freopen("shortcut.out", "w", stdout);
    fastio()
    #ifndef ONLINE_JUDGE
        freopen("errorf.in","w",stderr);
    #endif
    ll int t=1;
    // cin >> t;
    while(t--) solve();
    return 0;
}


    

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:316:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  316 |         freopen("errorf.in","w",stderr);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45