Submission #1247278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247278		Octa_pe_info	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	262 ms	25420 KiB

commuter_pass

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

struct arbore {

    bool directie;///0 = s->t , 1 = t->s

    long long nod,cost,stare,c_urcat;

    bool  operator>(const arbore & o)const {

        return cost > o.cost;
    }

/// 1. nu ne-am pus pe un drum cu 0 -> urcam pe unul <-> d[s][nod_curent] + cost + d[u][vecin]
///    acum, odata ce am "urcat pe o directie" s->t sau t->s, trebuie sa o mentin
///
/// +++ tinem costul cu care ne-am urcat prima data !!!
/// 2. sunt pe o secv de costuri 0 -> pot merge pe o muchie care e din acelasi drum minim
///    normal luand dupa directie, <-> atunci c_urcat + c_vecin + cost == dmin
///                                    daca e s->t atunci c_urcat creste
///                                    daca e t->s atunci c_urcat ... tot creste

///in fiecare punct cu stare 2 verificam rezultatul
};

struct arbore2 {

    long long nod,cost;

    bool operator>(const arbore2 & o)const {

        return cost > o.cost;
    }
};

vector<long long>ds,dt,dv,du;
vector<vector<arbore2>>tabel;
long long dp[100001][2],dmin=1e18,rez=1e18;///nodul, directie, folosim doar cand stare == 1, altfel doar du

///dijkstra normal

void dijksrtra1(vector<long long> & d,long long start) {

    priority_queue<arbore2,vector<arbore2>,greater<arbore2>>pq;

    pq.push({start,0});

    d[start] = 0;

    while(!pq.empty()) {

        auto curent = pq.top();
        pq.pop();

        if(d[curent.nod] < curent.cost)
            continue;

        for(auto i : tabel[curent.nod]) {

            if(d[i.nod] > curent.cost + i.cost) {

                d[i.nod] = curent.cost + i.cost;
                pq.push({i.nod,d[i.nod]});
            }
        }
    }
}

///acum e acum
///dijkstra principala

void dijksrtra2(long long u,long long v,long long s,long long t) {

    ///acum initializez in main dp sa fie doar chestii mari

    priority_queue<arbore,vector<arbore>,greater<arbore>>pq;

    pq.push({0,u,0,0,0});

    du[u] = 0;

    while(!pq.empty()) {

        auto curent = pq.top();
        pq.pop();

        if(curent.stare == 0) { ///nu am urcat inca in tren

            if(du[curent.nod] < curent.cost)
                continue;

            for(auto i : tabel[curent.nod]) {

                ///acum putem continua normal sau sa urcam

                ///normal

                if(du[i.nod] > curent.cost + i.cost){

                    du[i.nod] = curent.cost + i.cost;
                    pq.push({0,i.nod,du[i.nod],0,0});
                }

                ///acum putem urca

                ///s->t

                //cout<<ds[curent.nod] + i.cost + dt[i.nod]<<'\n';

                if(ds[curent.nod] + i.cost + dt[i.nod] == dmin && dp[i.nod][0] > curent.cost + dv[i.nod]){

                    dp[i.nod][0] = curent.cost + dv[i.nod];
                    rez = min(rez, dp[i.nod][0]);

                    pq.push({0,i.nod,curent.cost,1,ds[curent.nod] + i.cost});
                }

                ///t->s

                //cout<<dt[curent.nod] + i.cost + ds[i.nod]<<'\n';

                if(dt[curent.nod] + i.cost + ds[i.nod] == dmin && dp[i.nod][1] > curent.cost + dv[i.nod]){

                    dp[i.nod][1] = curent.cost + dv[i.nod];
                    rez = min(rez, dp[i.nod][1]);

                    pq.push({1,i.nod,curent.cost,1,dt[curent.nod] + i.cost});
                }
            }

        }

        if(curent.stare == 1){

            if(curent.directie == 1){///t->s

                if(dp[curent.nod][1] < curent.cost + dv[curent.nod])
                    continue;

                for(auto i : tabel[curent.nod]){

                    if(curent.c_urcat + i.cost + ds[i.nod] == dmin && dp[i.nod][1] > curent.cost + dv[i.nod]){

                        dp[i.nod][1] = curent.cost + dv[i.nod];
                        rez = min(rez,dp[i.nod][1]);

                        pq.push({1,i.nod,curent.cost,1,curent.c_urcat + i.cost});
                    }
                }
            }

            if(curent.directie == 0){///s->t

                if(dp[curent.nod][0] < curent.cost + dv[curent.nod])
                    continue;

                for(auto i : tabel[curent.nod]){

                    if(curent.c_urcat + i.cost + dt[i.nod] == dmin && dp[i.nod][0] > curent.cost + dv[i.nod]){

                        dp[i.nod][0] = curent.cost + dv[i.nod];
                        rez = min(rez,dp[i.nod][0]);

                        pq.push({0,i.nod,curent.cost,1,curent.c_urcat + i.cost});
                    }
                }
            }
        }

    }
}

int main() {

    long long n,m;
    cin>>n>>m;

    long long s,t,u,v;

    cin>>s>>t>>u>>v;

    dt.resize(n+1,1e18);
    ds.resize(n+1,1e18);
    du.resize(n+1,1e18);
    dv.resize(n+1,1e18);

    tabel.resize(n+1);

    for(long long i=1;i<=n;i++)
        dp[i][0] = dp[i][1] = 1e18;

    for(long long i=1;i<=m;i++){

        long long a,b,c;
        cin>>a>>b>>c;

        tabel[a].push_back({b,c});
        tabel[b].push_back({a,c});
    }

    dijksrtra1(dt,t);
    dijksrtra1(ds,s);
    dijksrtra1(dv,v);

    dmin = ds[t];
    rez = dv[u];

    dijksrtra2(u,v,s,t);

    cout<<rez;

    return 0;
}

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