Submission #1218536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218536		YassirSalama	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	499 ms	32180 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
using ull=unsigned long long;
using pii=pair<int,int>;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
template <typename T> istream& operator>>(istream& is, vector<T> &a) {
    copy_n(istream_iterator<T>(is), a.size(), a.begin()); return is;}
#ifdef IOI
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define pb push_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
const int mod = 1000000007;
const int maxn = 1e5+100;
int n;
vector<pair<int,int>> v[maxn];
vector<int> dij(int src){
    bool visited[maxn];
    memset(visited,false,sizeof(visited));
    vector<int> d(n+1,1e18);
    priority_queue<pair<int,int>> q;
    d[src]  =0;
    q.push({0,src});
    while(!q.empty()){
        auto [di,node] = q.top();
        q.pop();
        if(visited[node]) continue;
        visited[node] = 1;
        for(auto x : v[node]){
            if(d[x.F]>d[node]+x.S){
                d[x.F] = d[node]+x.S;
                q.push({-d[x.F],x.F});
            }
        }
    }
    return d;
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int m;
    cin>>n>>m;
    int s,t,a,b;
    cin>>s>>t>>a>>b;
    for(int i = 0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    vector<int> ds = dij(s),dt = dij(t);
    int D = ds[t];
    priority_queue<vector<int>> q;
    vector<vector<int>> d(n+1,vector<int>(3,1e18));
    /*
    d[node] = 0, we didn't enter some min path
    d[node] = 1, we enter a min path but we didn't leave yet
    d[node] = 2, we left the min path
    */
    d[a][0] = 0;
    q.push({-d[a][0],a,0});
    bool visited[n+1][3];memset(visited,false,sizeof(visited));
    auto check = [&](int x,int y,int c){
        if(ds[x]+dt[y]+c==D){
            return true;
        }
        return false;
    };
    while(!q.empty()){
        int node = q.top()[1],t = q.top()[2];
        q.pop();
        if(visited[node][t]) continue;
        visited[node][t] = 1;
        for(auto x : v[node]){
            if(t==0){
                //do with 0
                if(d[x.F][0]>d[node][0]+x.S){
                    d[x.F][0] = d[node][0]+x.S;
                    q.push({-d[x.F][0],x.F,0});
                }
                if(check(node,x.F,x.S)&&d[x.F][1]>d[node][0]){
                    d[x.F][1] = d[node][0];
                    q.push({-d[x.F][1],x.F,1});
                }
            }else if(t==1){
                if(check(node,x.F,x.S)&&d[x.F][1]>d[node][1]){
                    d[x.F][1] = d[node][1];
                    q.push({-d[x.F][1],x.F,1});
                }
                if(d[x.F][2]>d[node][1]+x.S){
                    d[x.F][2] = d[node][1] + x.S;
                    q.push({-d[x.F][2],x.F,2});
                }
            }else{
                if(d[x.F][2]>d[node][2]+x.S){
                    d[x.F][2] = d[node][2]+x.S;
                    q.push({-d[x.F][2],x.F,2});
                }
            }
        }
    }
    int ans1 = min({d[b][0],d[b][1],d[b][2]});
    memset(visited,false,sizeof(visited));
    auto check2 = [&](int x,int y,int c){
        if(dt[x]+ds[y]+c==D){
            return true;
        }
        return false;
    };
    d.assign(n+1,vector<int>(3,1e18));
    d[a][0] = 0;
    q.push({-d[a][0],a,0});
    while(!q.empty()){
        int node = q.top()[1],t = q.top()[2];
        q.pop();
        if(visited[node][t]) continue;
        visited[node][t] = 1;
        for(auto x : v[node]){
            if(t==0){
                //do with 0
                if(d[x.F][0]>d[node][0]+x.S){
                    d[x.F][0] = d[node][0]+x.S;
                    q.push({-d[x.F][0],x.F,0});
                }
                if(check2(node,x.F,x.S)&&d[x.F][1]>d[node][0]){
                    d[x.F][1] = d[node][0];
                    q.push({-d[x.F][1],x.F,1});
                }
            }else if(t==1){
                if(check2(node,x.F,x.S)&&d[x.F][1]>d[node][1]){
                    d[x.F][1] = d[node][1];
                    q.push({-d[x.F][1],x.F,1});
                }
                if(d[x.F][2]>d[node][1]+x.S){
                    d[x.F][2] = d[node][1] + x.S;
                    q.push({-d[x.F][2],x.F,2});
                }
            }else{
                if(d[x.F][2]>d[node][2]+x.S){
                    d[x.F][2] = d[node][2]+x.S;
                    q.push({-d[x.F][2],x.F,2});
                }
            }
        }
    }
    
    cout<<min({d[b][0],d[b][1],d[b][2],ans1})<<endl;
}

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