Submission #237079

#	Time	Username	Problem	Language	Result	Execution time	Memory
237079		aloo123	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	890 ms	24092 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define all(x) (x).begin() , (x).end()
#define f first
#define s second
#define pr(x) cout<<x<<endl;
#define pr2(x,y) cout<<x<<" "<<y<<endl;
#define pr3(x,y,z) cout<<x<<" "<<y<<endl;
#define prv(v) for(auto x:v) cout<<x<<" ";
#define ffs fflush(stdout);
#define int ll
#define sz(x) (ll)x.size()
using namespace std;
 
 
const ll MOD = 1e9+7;
const ll INF = LLONG_MAX;
const ll LOG = 29;
#define PI 3.141592653589793238 
 
 
 


const ll N =(1e5+5);

ll fact[N];

long long binpow(long long a, long long b) {
     a%=MOD;    
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%MOD;
        a = (a * a)%MOD;
 
        
        b >>= 1;
    }
     res%=MOD;
    return res;
}
void ini(){
    fact[0] = 1;
    for(int i = 1;i < N;i++){
        fact[i] = (fact[i-1] * i)%MOD;
    }
}
ll ncr(ll n,ll r){
    ll ret = fact[n];
    ret = (ret * binpow(fact[r],MOD-2))%MOD;
    ret = (ret * binpow(fact[n-r],MOD-2))%MOD;
    return ret;
}
struct lol
{
    ll to;
    ll cst;
};

ll n,m;
ll s,t;
ll u,v;
vector<lol> adj[N];
ll dis[N][2];
pll dis2[N][2];//dis[x] {shortest path from s,shortest path of all the nodes which lie on the shortest path from s to x to u}
void dijk(ll x){
    priority_queue<pll,vector<pll>,greater<pll>> pq;
    pq.push(mp(0,x));
    ll i = 0;
    if(x == v)i = 1;
    dis[x][i] = 0;
    while(!pq.empty()){
        pll p = pq.top();
        pq.pop();
        for(auto y:adj[p.s]){
            if(dis[y.to][i] > dis[p.s][i] + y.cst){
                dis[y.to][i] = dis[p.s][i] + y.cst;
                pq.push(mp(dis[y.to][i],y.to));
            }
        }
    }
}
void dijk2(ll x){
    priority_queue<pair<pll,ll>,vector<pair<pll,ll>>,greater<pair<pll,ll> >> pq;
    ll i;
    if(x == s) i = 0;
    else i = 1;
    pair<pll,ll> lolz;
    lolz.f.f = 0;
    lolz.f.s = dis[x][i];    
    lolz.s = x;
    pq.push(lolz);
    dis2[x][i].f = 0;
    dis2[x][i].s = dis[x][i];
    while(!pq.empty()){
        pair<pll,ll> p = pq.top();
        pq.pop();
        for(auto y:adj[p.s]){
            if(dis2[y.to][i] > mp(dis2[p.s][i].f + y.cst,min(dis[y.to][i],dis2[p.s][i].s))){
                dis2[y.to][i] = mp(dis2[p.s][i].f + y.cst,min(dis[y.to][i],dis2[p.s][i].s));
                pq.push(mp(mp(dis2[y.to][i].f,dis2[y.to][i].s),y.to));
                //pq.push(mp(dis2[y.to][i].f,mp(dis2[y.to][i].s,y.to)));
            }
        }
    }
}



void solve(){
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 1;i <= m;i++){
        ll x,y,c;
        cin >> x >> y >> c;
        adj[x].pb({y,c});
        adj[y].pb({x,c});
    }               
    for(int i = 1;i<=n;i++){
        dis[i][0] = INF;
        dis[i][1] = INF;
    }
    dijk(u);
    dijk(v);
    for(int i =1;i<=n;i++){
        for(int j = 0;j<2;j++){
            dis2[i][j].f = INF;
            dis2[i][j].s = INF;
        }
    }
    dijk2(s);
    dijk2(t);
    ll ans = INF;
    pll k;k={INF,INF};
    for(int i =1;i<=n;i++){
        pll x = mp(dis2[i][0].f+dis2[i][1].f,dis2[i][0].s+dis2[i][1].s);
        k=min(k,x);
    }
    ans = min(ans,min(k.s,dis[v][0]));
    for(int i =1;i<=n;i++){
        for(int j = 0;j<2;j++){
            dis2[i][j].f = INF;
            dis2[i][j].s = INF;
        }
    }
    for(int i = 1;i<=n;i++){
        dis[i][0] = INF;
        dis[i][1] = INF;
    }

    swap(u,v);
    dijk(u);
    dijk(v);
    dijk2(s);
    dijk2(t);
    for(int i =1;i<=n;i++){
        pll x = mp(dis2[i][0].f+dis2[i][1].f,dis2[i][0].s+dis2[i][1].s);
        k=min(k,x);
    }
    
    ans = min(ans,min(k.s,dis[v][0]));

    cout << ans << endl;
}   

 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
       
 
     ll tt=1;
    while(tt--){
        solve();
    }    
}

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