Submission #1291980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291980		banmkh	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	275 ms	21004 KiB

commuter_pass

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

#define ll long long
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define arr2 array<int,2>
#define arr3 array<int,3>
#define arr4 array<int,4>
#define arr5 array<int,5>
#define el '\n'
#define pii pair<int,int>
#define __ <<' '<<
#define i128 __int128
#define IMPOSSIBLE return cout << "-1" << endl,void();
#define FILE "cowmbat"

const int N = 1e5 + 7;
const int MOD = 1e9 + 7;

vector<pii> e[N];

bool visited[N];

int res[4][N];

void dijstra1(int start,int type){
    priority_queue<pii, vector<pii>, greater<>> q;

    memset(res[type], 60, sizeof res[type]);
    
    q.push({0, start});
    
    res[type][start] = 0;
    
    while(sz(q)){
        auto [w,u] = q.top(); q.pop();

        if(w > res[type][u])continue;
        
        for(auto [v,wv] : e[u]){
            if(wv + w >= res[type][v])continue;
            res[type][v] = wv + w;
            q.push({wv + w, v});
        }
    }
}

int tmp[3][N];

void dijstra2(int start){

    memset(res[0],60,sizeof res[0]);
    memset(res[3],60,sizeof res[3]);
    memset(tmp[1],60,sizeof tmp[1]);
    memset(tmp[2],60,sizeof tmp[2]);
    
    res[0][start] = 0;
    tmp[1][start] = res[1][start];
    tmp[2][start] = res[2][start];
    res[3][start] = res[1][start] + res[2][start];
    // cout << res[1][start] __ res[2][start] << endl;

    priority_queue<pii, vector<pii>, greater<> > q;
    q.push({0,start});

    while(sz(q)){
        auto [w,u] = q.top();q.pop();
        if(w > res[0][u])continue;
        
        for(auto [v,wv] : e[u]){
            if(wv + w > res[0][v])continue;
            if(wv + w == res[0][v]){
                res[3][v] = min({res[3][u], res[3][v], res[2][v] + tmp[1][u], res[1][v] + tmp[2][u]});
                tmp[1][v] = min(tmp[1][v],tmp[1][u]);
                tmp[2][v] = min(tmp[2][v],tmp[2][u]);
            }
            else{
                res[0][v] = wv + w;
                res[3][v] = min({res[3][u], res[2][v] + tmp[1][u], res[1][v] + tmp[2][u], res[1][v] + res[2][v]});
                tmp[1][v] = min(tmp[1][u],res[1][v]);
                tmp[2][v] = min(tmp[2][u],res[2][v]);
                q.push({wv + w,v});
            }
        }
    }
}

void solve(){
    int n,m;
    cin >> n >> m;

    memset(res[1], 60, sizeof res[1]);
    memset(res[2], 60, sizeof res[2]);

    int S,T,U,V;
    cin >> S >> T >> U >> V;

    for(int i = 0;i < m; i++){
        int u,v,w;
        cin >> u >> v >> w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    int ans = LLONG_MAX;
    dijstra1(U,1);
    dijstra1(V,2);
    ans = res[1][V];
    dijstra2(S);
    ans = min(ans, res[3][T]);
    // // dijstra2(T);
    // // ans = min(ans,res[3][S]);

    cout << ans << endl;

}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("io\\ban.in","r",stdin);
    freopen("io\\ban.txt","w",stdout);
// #elif !(ONLINE_JUDGE)
//     freopen(FILE ".in","r",stdin);
//     freopen(FILE ".out","w",stdout);
#endif

    int q(1);
    // cin >> q;
    while(q--) solve();
    return 0;
}

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