제출 #1009237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009237		christinelynn	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	1882 ms	66740 KiB

commuter_pass

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

# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

void solve() {
    // cerr << "IN" << endl;
    int n, m; cin >> n >> m;

    int s, t; cin >> s >> t;
    int u, v; cin >> u >> v;

    vector<pair<int, int>> vec[cnst];

    tuple<int, int, int> edge[m+5];
    map<pair<int, int>, int> mp;
    int par[n+5];

    for(int i = 1; i<=m; i++) {
        int a, b, c; cin >> a >> b >> c;
        // cerr << a << " " << b << " " << c << endl;
        vec[a].pb({b, c});
        vec[b].pb({a, c});
        mp[{a, b}] = i;
        mp[{b, a}] = i;
        edge[i] = {a, b, c};
    }

    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.push({0, s, 0});

    bool vis[n+5];
    bool check[m+5];

    memset(vis, 0, sizeof(vis));
    memset(check, 0, sizeof(check));

    par[s] = 0;

    while(!pq.empty()) {
        auto[ene, idx, pr] = pq.top(); pq.pop();
        cerr << ene << " " << idx << " " << pr << endl;

        if(idx == t) {
            int now = t;
            par[now] = pr;
            while(par[now] != 0) {
                check[mp[{now, par[now]}]] = 1;
                now = par[now];
            }
        }

        if(vis[idx]) continue;
        vis[idx] = 1;
        par[idx] = pr;

        for(auto[v, wei]: vec[idx]) if(!vis[v]) {
            pq.push({ene+wei, v, idx});
        }
    }

    vector<pair<int, int>> vec2[n+5];

    for(int i = 1; i<=m; i++) 
    if(!check[i]) {
        auto[a, b, c] = edge[i];
        vec2[a].pb({b, c});
        vec2[b].pb({a, c});
    }
    else {
        auto[a, b, c] = edge[i];
        vec2[a].pb({b, 0});
        vec2[b].pb({a, 0});
    }

    memset(vis, 0, sizeof(vis));
    pq.push({0, u, 0});

    while(!pq.empty()) {
        auto[ene, idx, pr] = pq.top(); pq.pop();

        if(idx == v) {
            cout << ene << endl; return;
        }

        if(vis[idx]) continue;
        vis[idx] = 1;
        par[s] = pr;

        for(auto[v, wei]: vec2[idx]) if(!vis[v]) {
            pq.push({ene+wei, v, idx});
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

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