Submission #955220

#	Time	Username	Problem	Language	Result	Execution time	Memory
955220		sandry24	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	252 ms	21788 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

ll ans;
const ll maxn = 1e5+5, INF = 1e18;
vector<vector<pi>> adj(maxn);
vector<ll> distS(maxn, INF), distT(maxn, INF), distU(maxn, INF), distV(maxn, INF);
vector<ll> distUM(maxn, INF), distVM(maxn, INF); //dist from U and V to nodes on short paths

void Dijkstra(ll x, vector<ll> &dist){
    dist[x] = 0;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
    q.push({0, x});
    while(!q.empty()){
        int a = q.top().s;
        q.pop();
        for(auto u : adj[a]){
            int b = u.f, w = u.s;
            if(dist[a] + w < dist[b]){
                dist[b] = dist[a] + w;
                q.push({dist[b], b});
            }
        }
    }
}

void solve(){
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }

    Dijkstra(s, distS);
    Dijkstra(t, distT);
    Dijkstra(u, distU);
    Dijkstra(v, distV);

    ll ans = distU[v];
    vector<pair<ll, ll>> on_path;
    for(int i = 1; i <= n; i++)
        if(distS[i] + distT[i] == distS[t])
            on_path.pb({distS[i], i});
    sort(on_path.begin(), on_path.end()); //to not take 2 different paths in ans

    for(auto i : on_path){
        int x = i.s;
        distUM[x] = distU[x];
        distVM[x] = distV[x];
        for(auto j : adj[x]){
            if(distS[j.f] + j.s == distS[x]){ //we alr processed this node
                distUM[x] = min(distUM[x], distUM[j.f]);
                distVM[x] = min(distVM[x], distVM[j.f]);
            }
        }
        ans = min(ans, distUM[x] + distV[x]);
        ans = min(ans, distVM[x] + distU[x]);
    }

    cout << ans << '\n';
} 
 
int main(){
    // freopen("monede.in", "r", stdin);
    // freopen("monede.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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