Submission #422421

#	Time	Username	Problem	Language	Result	Execution time	Memory
422421		jlallas384	Commuter Pass (JOI18_commuter_pass)	C++17	31 / 100	499 ms	22052 KiB

commuter_pass

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

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");} 

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)

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]);
    };
    vector<ll> dist(n,1e17);
    vector<vector<int>> par(n);
    priority_queue<pair<ll,int>> pq;
    dist[s] = 0;
    pq.emplace(0,s);
    while(pq.size()){
        auto [dst,cur] = pq.top(); pq.pop();
        if(-dst > dist[cur]) continue;
        for(int id: g[cur]){
            int nxt = f(id,cur);
            ll nw = dist[cur] + get<2>(e[id]);
            if(nw < dist[nxt]){
                dist[nxt] = nw;
                pq.emplace(-nw,nxt);
                par[nxt].clear();
                par[nxt].push_back(id);
            }else if(nw == dist[nxt]){
                par[nxt].push_back(id);
            }
        }
    }
    stack<int> stk;
    stk.push(t);
    vector<int> vis(n);
    while(stk.size()){
        int cur = stk.top(); stk.pop();
        for(int id: par[cur]){
            get<2>(e[id]) = 0;
            if(!vis[f(id,cur)]){
                stk.push(f(id,cur));
                vis[f(id,cur)] = 1;
            }
        }
    }
    dist = vector<ll>(n,1e17);
    dist[u] = 0;
    pq.emplace(0,u);
    while(pq.size()){
        auto [dst,cur] = pq.top(); pq.pop();
        if(-dst > dist[cur]) continue;
        for(int id: g[cur]){
            int nxt = f(id,cur);
            ll nw = dist[cur] + get<2>(e[id]);
            if(nw < dist[nxt]){
                dist[nxt] = nw;
                pq.emplace(-nw,nxt);
            }
        }
    }
    cout << dist[v];
}

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