제출 #380772

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

commuter_pass

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

int main(){
    int n,m,s,t,u,v;
    cin >> n >> m >> s >> t >> u >> v,s--,t--,u--,v--;
    vector<vector<int>> g(n);
    vector<tuple<int,int,int>> e;
    for(int i = 0; i < m; i++){
        int a,b,c;
        cin >> a >> b >> c,a--,b--;
        g[a].push_back(i);
        g[b].push_back(i);
        e.emplace_back(a,b,c);
    }
    auto f = [&](int i,int x){
        return x ^ get<0>(e[i]) ^ get<1>(e[i]);
    };
    auto dijkstra = [&](int from,int to){
        vector<ll> dist(n,1e17),par(n,-1);
        dist[from] = 0;
        priority_queue<pair<ll,int>> pq;
        pq.emplace(0,from);
        while(pq.size()){
            auto [d,cur] = pq.top(); pq.pop();
            if(-d > dist[cur]) continue;
            for(int nxt: g[cur]){
                int other = f(nxt,cur),cst = get<2>(e[nxt]);
                if(dist[cur] + cst < dist[other]){
                    dist[other] = dist[cur] + cst;
                    pq.emplace(-dist[other],other);
                    par[other] = nxt;
                }
            }
        }
        ll res = dist[to];
        while(to != from){
            get<2>(e[par[to]]) = 0;
            to = f(par[to],to);
        }
        return res;
    };
    dijkstra(s,t);
    cout << dijkstra(u,v);

}

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