Submission #1153617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153617		minhpk	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2097 ms	55848 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
int a,b;
int s,t;
int u,v;
vector <pair<int,int>> z[1000000];
int cnt1[1000000];
int cnt2[1000000];
int cnt[1000000][3];
int bruh=1e9;
struct node{
     int nxt,val,fri;
};
vector <node> z1[200005];
vector <node> z2[200005];
struct node1{
     int val1,pos1,type;
};
struct compare{
     bool operator()(node1 a,node1 b){
          return a.val1<b.val1;
     }
};
void dijkstras(){
     for (int i=1;i<=a;i++){
         cnt1[i]=bruh;
     }

     priority_queue<pair<int,int> ,  vector<pair<int,int> > , greater<pair<int,int> > > q;
     q.push({0,s});
     cnt1[s]=0;

     while (q.size()){
         pair<int,int> pos=q.top();
         q.pop();
         int val=pos.first;
         int pos1=pos.second;

         if (val>cnt1[pos1]){
            continue;
         }
         for (auto p:z[pos1]){
            if (cnt1[p.first]>val+p.second){
                cnt1[p.first]=val+p.second;
                q.push({cnt1[p.first],p.first});
            }
         }
     }
}


void dijkstrat(){
     for (int i=1;i<=a;i++){
         cnt2[i]=bruh;
     }

     priority_queue<pair<int,int> ,  vector<pair<int,int> > , greater<pair<int,int> > > q;
     q.push({0,t});
     cnt2[t]=0;

     while (q.size()){
         pair<int,int> pos=q.top();
         q.pop();
         int val=pos.first;
         int pos1=pos.second;

         if (val>cnt2[pos1]){
            continue;
         }
         for (auto p:z[pos1]){
            if (cnt2[p.first]>val+p.second){
                cnt2[p.first]=val+p.second;
                 q.push({cnt2[p.first],p.first});

            }
         }
     }
}

void dijkstra(){
    for (int i=1;i<=a;i++){
         for (int j=0;j<=2;j++){
              cnt[i][j]=bruh;
         }
    }

    priority_queue< node1 , vector <node1> , compare > q;
    q.push({0,u,0});
    cnt[u][0]=0;

    while (q.size()){
        node1 pos=q.top();
        q.pop();
        int val=pos.val1;
        int pos1=pos.pos1;
        int type=pos.type;

        if (val>cnt[pos1][type]){
            continue;
        }

        for (auto p:z1[pos1]){
            if (type==0){
                if (cnt[p.nxt][type]>val+p.val){
                    cnt[p.nxt][type]=val+p.val;
                    q.push({cnt[p.nxt][type],p.nxt,type});
                }
                if (p.fri==0){
                    if (cnt[p.nxt][1]>val){
                       cnt[p.nxt][1]=val;
                       q.push({cnt[p.nxt][1],p.nxt,1});
                    }
                }
            }else if (type==1){
                if (p.fri==0){
                    if (cnt[p.nxt][1]>val){
                       cnt[p.nxt][1]=val;
                       q.push({cnt[p.nxt][1],p.nxt,1});
                    }
                }
                    if (cnt[p.nxt][2]>val+p.val){
                        cnt[p.nxt][2]=val+p.val;
                        q.push({cnt[p.nxt][2],p.nxt,2});
                    }

            }else{
                if (cnt[p.nxt][type]>val+p.val){
                    cnt[p.nxt][type]=val+p.val;
                    q.push({cnt[p.nxt][type],p.nxt,type});
                }
            }
        }

    }
}



void dijkstra1(){
    for (int i=1;i<=a;i++){
         for (int j=0;j<=2;j++){
              cnt[i][j]=bruh;
         }
    }

    priority_queue< node1 , vector <node1> , compare > q;
    q.push({0,u,0});
    cnt[u][0]=0;

    while (q.size()){
        node1 pos=q.top();
        q.pop();
        int val=pos.val1;
        int pos1=pos.pos1;
        int type=pos.type;

        if (val>cnt[pos1][type]){
            continue;
        }

        for (auto p:z2[pos1]){
            if (type==0){
                if (cnt[p.nxt][type]>val+p.val){
                    cnt[p.nxt][type]=val+p.val;
                    q.push({cnt[p.nxt][type],p.nxt,type});
                }
                if (p.fri==0){
                    if (cnt[p.nxt][1]>val){
                       cnt[p.nxt][1]=val;
                       q.push({cnt[p.nxt][1],p.nxt,1});
                    }
                }
            }else if (type==1){
                if (p.fri==0){
                    if (cnt[p.nxt][1]>val){
                       cnt[p.nxt][1]=val;
                       q.push({cnt[p.nxt][1],p.nxt,1});
                    }
                }
                    if (cnt[p.nxt][2]>val+p.val){
                        cnt[p.nxt][2]=val+p.val;
                        q.push({cnt[p.nxt][2],p.nxt,2});
                    }

            }else{
                if (cnt[p.nxt][type]>val+p.val){
                    cnt[p.nxt][type]=val+p.val;
                    q.push({cnt[p.nxt][type],p.nxt,type});
                }
            }
        }

    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    cin >> s >> t;
    cin >> u >> v;

    for (int i=1;i<=b;i++){
         int x,y,t;
         cin >> x >> y >> t;
         z[x].push_back({y,t});
         z[y].push_back({x,t});
    }

    dijkstras();
    dijkstrat();
   //cout << cnt1[t] << "\n";
    for (int i=1;i<=a;i++){
        for (auto p:z[i]){
            int chisoan1=-1;
            int chisoan=-1;
            int y=p.first;
            int val=p.second;
            int x=i;
            if (cnt1[x]+cnt2[y]+val==cnt1[t]){
                 chisoan=0;
            }else if (cnt1[y]+cnt2[x]+val==cnt1[t]){
                 chisoan1=0;
            }
            z2[x].push_back({y,val,chisoan1});
            z1[x].push_back({y,val,chisoan});
           // if (chisoan==0){
           //     cout << x << " " << y << "\n";
           // }
        }
    }

    dijkstra();

    //cout << cnt[4][1] << "\n";
    int min1=min({cnt[v][0],cnt[v][1],cnt[v][2]});
    dijkstra1();
    min1=min({min1,cnt[v][0],cnt[v][1],cnt[v][2]});
    cout << min1;

    return 0;
}

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