Submission #233741

#	Time	Username	Problem	Language	Result	Execution time	Memory
233741		nicolaalexandra	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	778 ms	44000 KiB

commuter_pass

#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000000000000LL
using namespace std;

priority_queue <pair<long long,int>, vector<pair<long long,int> >, greater<pair<long long,int> > > H;
priority_queue <pair<long long,pair<int,int> >, vector<pair<long long,pair<int,int> > >, greater <pair<long long,pair<int,int> > > > c;
vector <pair<int,long long> > L[DIM];
vector <int> fth[DIM],edg[DIM];
long long dist_s[DIM],dist_u[DIM],dist_t[DIM],dp[DIM][5];
int viz[DIM];
int n,m,s,t,x,y,i,u,v;
long long cost;
void dfs (int nod){
    viz[nod] = 1;
    for (auto vecin : fth[nod])
        if (!viz[vecin]){
            edg[vecin].push_back(nod);
            dfs (vecin);
        }
}

void dijkstra (long long dp[], int start){

    for (i=1;i<=n;i++)
        dp[i] = INF;
    dp[start] = 0;

    while (!H.empty())
        H.pop();
    //H.clear();
    H.push (make_pair(0,start));
    while (!H.empty()){
        int nod = H.top().second;
        long long cost = H.top().first;
        H.pop();
        if (dp[nod] < cost)
            continue;
        for (auto it : L[nod]){
            int vecin = it.first; long long new_cost = it.second;
            if (dp[nod] + new_cost < dp[vecin]){
                dp[vecin] = dp[nod] + new_cost;
                H.push(make_pair(dp[vecin],vecin));
            }}}}

int main (){

   // ifstream cin ("date.in");
   // ofstream cout ("date.out");

    cin>>n>>m>>s>>t>>u>>v;
    for (i=1;i<=m;i++){
        cin>>x>>y>>cost;
        L[x].push_back(make_pair(y,cost));
        L[y].push_back(make_pair(x,cost));
    }

    for (i=1;i<=n;i++)
        dist_s[i] = INF;
    dist_s[s] = 0;
    H.push(make_pair(0,s));
    while (!H.empty()){
        int nod = H.top().second;
        long long cost = H.top().first;
        H.pop();
        if (dist_s[nod] < cost)
            continue;
        for (auto it : L[nod]){
            int vecin = it.first; long long new_cost = it.second;
            if (dist_s[nod] + new_cost < dist_s[vecin]){
                dist_s[vecin] = dist_s[nod] + new_cost;
                fth[vecin].clear();
                fth[vecin].push_back(nod);
                H.push(make_pair(dist_s[vecin],vecin));
            } else {
                if (dist_s[nod] + new_cost == dist_s[vecin])
                    fth[vecin].push_back(nod);
            }}}

    /// marchez toate nodurile care se afla pe drumurile minime de la S la T
    viz[t] = 1;
    dfs (t);

    //dijkstra (dist_u,u);
    //dijkstra (dist_v,v);
    dijkstra (dist_t,t);

    /// dp[nod][stare] - distanta minima de la u la un nod

    /// 0 - nu am intrat pe un drum minim
    /// 1 - merg pe un drum minim spre t
    /// 2 - merg pe un drum minim spre s
    /// 3 - am mers pe un drum minim, dar acum nu mai sunt

    for (i=1;i<=n;i++)
        dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = INF;

    dp[u][0] = 0;
    c.push(make_pair(0,make_pair(u,0)));

    if (viz[u]){
        dp[u][1] = dp[u][2] = 0;
        c.push(make_pair(0,make_pair(u,1)));
        c.push(make_pair(0,make_pair(u,2)));
    }

    while (!c.empty()){
        int nod = c.top().second.first;
        int stare = c.top().second.second;
        long long cost = c.top().first;
        c.pop();
        if (dp[nod][stare] < cost)
            continue;

        for (auto it : L[nod]){
            int vecin = it.first; long long new_cost = it.second;
            if (stare == 0){

                if (dp[nod][stare] + new_cost < dp[vecin][stare]){
                    dp[vecin][stare] = dp[nod][stare] + new_cost;
                    c.push(make_pair(dp[vecin][stare],make_pair(vecin,stare)));
                }

                if (viz[vecin]){ /// pot sa actualizez dp[vecin][1/2]

                    if (dp[nod][stare] + new_cost < dp[vecin][1]){
                        dp[vecin][1] = dp[nod][stare] + new_cost;
                        c.push(make_pair(dp[vecin][1],make_pair(vecin,1)));
                    }

                    if (dp[nod][stare] + new_cost < dp[vecin][2]){
                        dp[vecin][2] = dp[nod][stare] + new_cost;
                        c.push(make_pair(dp[vecin][2],make_pair(vecin,2)));
                    }}

            } else {
                if (stare == 1){

                    if (dist_s[vecin] + new_cost + dist_t[nod] == dist_s[t]){ /// pot sa pastrez starea asta
                        if (dp[nod][stare] < dp[vecin][stare]){
                            dp[vecin][stare] = dp[nod][stare];
                            c.push(make_pair(dp[vecin][stare],make_pair(vecin,stare)));
                        }
                    }

                    /// trec in starea 3

                    if (dp[nod][stare] + new_cost < dp[vecin][3]){
                        dp[vecin][3] = dp[nod][stare] + new_cost;
                        c.push(make_pair(dp[vecin][3],make_pair(vecin,3)));
                    }

                } else {
                    if (stare == 2){

                        if (dist_s[nod] + new_cost + dist_t[vecin] == dist_s[t]){ /// pot sa pastrez starea asta
                            if (dp[nod][stare] < dp[vecin][stare]){
                                dp[vecin][stare] = dp[nod][stare];
                                c.push(make_pair(dp[vecin][stare],make_pair(vecin,stare)));
                            }
                        }

                        /// trec in starea 3
                        if (dp[nod][stare] + new_cost < dp[vecin][3]){
                            dp[vecin][3] = dp[nod][stare] + new_cost;
                            c.push(make_pair(dp[vecin][3],make_pair(vecin,3)));
                        }

                    } else { /// stare == 3
                        /// acum pot doar sa trec in starea 3
                        if (dp[nod][stare] + new_cost < dp[vecin][stare]){
                            dp[vecin][stare] = dp[nod][stare] + new_cost;
                            c.push(make_pair(dp[vecin][stare],make_pair(vecin,stare)));
                        }}}}}}


    cout<<min(min(dp[v][0],dp[v][1]),min(dp[v][2],dp[v][3]));


    return 0;
}

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