제출 #1311670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311670		krasnal738	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	666 ms	82336 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[4 * 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(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){
    int n = graf.size() / 4;
    for(auto [u, v, w] : git){
        graf[n + u].push_back({n + v, w});
        graf[2 * n + v].push_back({2 * n + u, w});
    }
}

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

    vector<vector<pair<ll, int>>> graf(n + 1), graf2(4 * n + 1);
    for(int i = 1; i <= n; i++){
        graf2[i].push_back({n + i, 0});
        graf2[i].push_back({2 * n + i, 0});
        graf2[n + i].push_back({3 * n + i, 0});
        graf2[2 * n + i].push_back({3 * n + i, 0});
        odl_s[i] = inf;
        odl_t[i] = inf;
        // odl_u[i] = inf;
    }
    fill(odl_u, odl_u + 4 * MAXN, inf);

    vector<edge> edges(m);
    for(edge &e : edges){
        e.wczyt();
        graf[e.u].push_back({e.v, e.w});
        graf[e.v].push_back({e.u, e.w});
        
        graf2[e.u].push_back({e.v, e.w});
        graf2[e.v].push_back({e.u, e.w});

        graf2[3 * n + e.u].push_back({3 * n + e.v, e.w});
        graf2[3 * n + e.v].push_back({3 * n + e.u, e.w});
    }

    dijkstra(s, odl_s, graf);
    dijkstra(t, odl_t, graf);
    vector<edge> git;
    which_edges(s, t, edges, git);
    build_graf(graf2, git);
    dijkstra(u, odl_u, graf2);

    cout << odl_u[3 * n + v] << '\n';
}

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