제출 #338302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
338302		gozonite	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	570 ms	25364 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<pair<int, int>> vii;
typedef pair<int, int> pi;
#define MOD 1000000007LL

int N, M, S, T, U, V;
vector<pair<int, ll>> adj[100001];
ll disu[100001], disv[100001], diss[100001];
bool vis[100001];
bool indag[100001]={false};
ll dpu[100001], dpv[100001]; // shortest path from u/v to node in dag (where edges are 0 in dag --> cascade)

void dij(int s, ll (&dis)[100001]) {
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= N; i++) dis[i] = 1e18;
    dis[s] = 0;
    using T = pair<ll, ll>; priority_queue<T, vector<T>, greater<T>> q;
    q.push({0, s});
    while (!q.empty()) {
        int v = q.top().second; q.pop();
        if (vis[v]) continue;
        vis[v] = true;
        for (auto pp : adj[v]) {
            ll u = pp.first, w = pp.second;
            if (dis[v]+w < dis[u]) {
                dis[u] = dis[v]+w;
                q.push({dis[u], u});
            }
        }
    }
}

void cdag(int v) {
    if (indag[v]) return;
    indag[v] = true;
    for (auto pp : adj[v]) {
        ll u = pp.first, w = pp.second;
        if (diss[u]+w == diss[v]) cdag(u);
    }
}

// starting from S to T
ll rdpu(int v) {
    if (dpu[v] != -1) return dpu[v];
    ll res = disu[v];
    for (auto pp : adj[v]) {
        ll u = pp.first, w = pp.second;
        if (indag[u] && diss[u]+w == diss[v]) res = min(res, rdpu(u));
    }
    return dpu[v] = res;
}

// starting from T to S
ll rdpv(int v) {
    if (dpv[v] != -1) return dpv[v];
    ll res = disv[v];
    for (auto pp : adj[v]) {
        ll u = pp.first, w = pp.second;
        if (indag[u] && diss[v]+w == diss[u]) res = min(res, rdpv(u));
    }
    return dpv[v] = res;
}

int main() {
    //freopen("feast.in", "r", stdin);
    //freopen("feast.out", "w", stdout);
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    
    cin >> N >> M >> S >> T >> U >> V;
    for (int i = 0; i < M; i++) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    
    dij(U, disu); dij(V, disv); dij(S, diss);
    //cout << "Debugging dijkstras" << endl;
    //for (int i = 1; i <= N; i++) cout << disu[i] << " "; cout << endl;
    //for (int i = 1; i <= N; i++) cout << disv[i] << " "; cout << endl;
    //for (int i = 1; i <= N; i++) cout << diss[i] << " "; cout << endl;
    
    cdag(T);
    //cout << "Debugging nodes in dag" << endl;
    //for (int i = 1; i <= N; i++) cout << indag[i] << " "; cout << endl;
    
    for (int i = 1; i <= N; i++) {
        if (indag[i]) {
            dpu[i] = -1; //disu[i];
            dpv[i] = -1; //disv[i];
        } else {
            dpu[i] = 1e18;
            dpv[i] = 1e18;
        }
    }
    
    // first case: U is closer to S
    rdpu(T); rdpv(S);
    //cout << "Debugging dps" << endl;
    //for (int i = 1; i <= N; i++) cout << dpu[i] << " "; cout << endl;
    //for (int i = 1; i <= N; i++) cout << dpv[i] << " "; cout << endl;
    
    ll ans = disu[V];
    for (int i = 1; i <= N; i++)
        if (indag[i]) ans = min(ans, dpu[i]+dpv[i]);
        
    // second case: U is closer to T
    for (int i = 1; i <= N; i++) {
        if (indag[i]) {
            dpv[i] = -1;
            dpu[i] = -1;
        } else {
            dpv[i] = 1e18;
            dpu[i] = 1e18;
        }
    }
    swap(disu, disv);
    rdpu(T); rdpv(S);
    for (int i = 1; i <= N; i++)
        if (indag[i]) ans = min(ans, dpu[i]+dpv[i]);
    
    //cout << "Debugging dps2" << endl;
    //for (int i = 1; i <= N; i++) cout << dpu[i] << " "; cout << endl;
    //for (int i = 1; i <= N; i++) cout << dpv[i] << " "; cout << endl;
    
    cout << ans << endl;
}

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