Submission #833680

#	Time	Username	Problem	Language	Result	Execution time	Memory
833680		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	185 ms	20848 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, int>
#define fi first
#define se second
const int ar = 1e5 + 5;
int n, m, u, v, s, t;
ll dp[ar][2], dis[ar];
vector<pii> adj[ar];
int x[ar << 1], y[ar << 1], w[ar << 1];

void dijktra(int u, int c) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, u});
    dp[u][c] = 0;
    while(q.size()) {
        int vt = q.top().se; ll kc = q.top().fi; q.pop();
//        cout << vt << ' ' << kc << '\n';
        if(kc > dp[vt][c]) continue;
        for(auto x : adj[vt]) {
            if(dp[x.se][c] > dp[vt][c] + x.fi) {
                dp[x.se][c] = dp[vt][c] + x.fi;
                q.push({dp[x.se][c], x.se});
            }
        }
    }
}

void dijktra2(int u) {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0, u});
    dis[u] = 0;
    while(q.size()) {
        int vt = q.top().se; ll kc = q.top().fi; q.pop();
        if(kc > dis[vt]) continue;
        for(auto x : adj[vt]) {
            ll cost = x.fi;
            if(dp[x.se][0] + dp[vt][1] + x.fi == dp[t][0]) cost = 0;
            if(dp[vt][0] + dp[x.se][1] + x.fi == dp[v][0]) cost = 0;
            if(dis[x.se] > dis[vt] + cost) {
                dis[x.se] = dis[vt] + cost;
                q.push({dis[x.se], x.se});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 1; i <= m; ++i) {
        cin >> x[i] >> y[i] >> w[i];
        adj[x[i]].push_back({w[i], y[i]});
        adj[y[i]].push_back({w[i], x[i]});
    }
    memset(dp, 0x3f, sizeof(dp));
    dijktra(s, 0);
    dijktra(t, 1);
    dijktra2(u);
//    for(int i = 1; i <= n; ++i) {
//        cout << i << ' ' << dp[i][0] << ' ' << dp[i][1] << '\n';
//    }
    cout << dis[v];
}

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