Submission #1311608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311608		krasnal738	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	532 ms	56760 KiB

commuter_pass

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

#define ll long long

struct edge{
    int u, v;
    ll w;
    void wczyt(){
        cin >> u >> v >> w;
    }

    void print(){
        cerr << u << ' ' << v << ' ' << w << '\n'; 
    }
};

const int MAXN = 1e5 + 7;
const ll inf = 1e18;
ll odl_s[MAXN], odl_t[MAXN], odl_u[MAXN];

void dijkstra(int start, ll odl[], vector<vector<pair<ll, int>>> &graf){
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, start});

    while(!pq.empty()){
        auto [cost, v] = pq.top();
        // cerr << "v: " << v << " cost: " << cost << '\n';
        pq.pop();
        if(odl[v] != inf) continue;
        odl[v] = cost;
        for(auto [u, w] : graf[v]){
            // cerr << "u: " << u << " w: " << w << "\n";
            if(odl[u] == inf) pq.push({cost + w, u});
        }
    }
    // cerr << "###################\n";
}

void which_edges(int s, int t, vector<edge> &edges, vector<edge> &vec){
    for(auto [u, v, w] : edges){
        if((u == s || u == t) && (v == s || v == t)) continue;
        if(odl_s[u] + w + odl_t[v] == odl_s[t]) vec.push_back({u, v, 0});
        if(odl_s[v] + w + odl_t[u] == odl_s[t]) vec.push_back({v, u, 0});
    }
}

void build_graf(vector<vector<pair<ll, int>>> &graf, vector<edge> &git, bool mod){
    for(auto [u, v, w] : git){
        if(mod) swap(u, v);
        graf[u].push_back({v, w});
    }
}

int main(){
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;

    for(int i = 1; i <= n; i++){
        odl_s[i] = inf;
        odl_t[i] = inf;
        odl_u[i] = inf;
    }

    vector<edge> edges(m);
    vector<vector<pair<ll, int>>> graf(n + 1);
    for(edge &e : edges){
        e.wczyt();
        graf[e.u].push_back({e.v, e.w});
        graf[e.v].push_back({e.u, e.w});
    }

    dijkstra(s, odl_s, graf);
    dijkstra(t, odl_t, graf);
    vector<edge> git;
    which_edges(s, t, edges, git);
    // for(edge e : git){
    //     e.print();
    // }
    // cerr << "------------------\n";

    vector<vector<pair<ll, int>>> graf1, graf2;
    graf1 = graf2 = graf;
    build_graf(graf1, git, 0);
    build_graf(graf2, git, 1);

    dijkstra(u, odl_u, graf1);
    ll ans = odl_u[v];
    for(int i = 1; i <= n; i++) odl_u[i] = inf;
    dijkstra(u, odl_u, graf2);
    ans = min({ans, odl_u[v], odl_u[s] + odl_t[v], odl_u[t] + odl_s[v]});
    cout << ans << '\n';
}

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