Submission #650030

#	Time	Username	Problem	Language	Result	Execution time	Memory
650030		HaYoungJoon	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	394 ms	23944 KiB

commuter_pass

#include <bits/stdc++.h>
#define ll long long
#define INF 1e18

using namespace std;

typedef pair<ll,ll> pii;
const int maxn = 1e5 + 1;
int n,m,S,T,U,V;
ll dist[2][maxn], dp[2][maxn], d[maxn];
vector<pii> adj[maxn];

void dijsktra1(int id, int s) {
    for (int i = 1; i <= n; i++) {
        dist[id][i] = INF;
    }
    dist[id][s] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push(pii(0,s));
    while (!pq.empty()) {
        ll u = pq.top().second, D = pq.top().first;
        pq.pop();
        if (D > dist[id][u]) continue;
        for (pii i: adj[u]) {
            int v = i.first;
            ll w = i.second;
            if (D+w < dist[id][v]) {
                dist[id][v] = D + w;
                pq.push(pii(dist[id][v],v));
            }
        }
    }
}

ll dijsktra2(int s, int f) {
    for (int i = 0; i <= n; i++) {
        d[i] = dp[0][i] = dp[1][i] = INF;
    }
    d[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push(pii(0,s));
    dp[0][s] = dist[0][s];
    dp[1][s] = dist[1][s];
    while (!pq.empty()) {
        ll u = pq.top().second, D = pq.top().first;
        pq.pop();
        if (D > d[u]) continue;
        for (pii i: adj[u]) {
            int v = i.first;
            ll w = i.second;
            if (D+w == d[v] && min(dp[0][u],dist[0][v]) + min(dp[1][u],dist[1][v]) <= dp[0][v] + dp[1][v]) {
                dp[0][v] = min(dp[0][u],dist[0][v]);
                dp[1][v] = min(dp[1][u],dist[1][v]);
            } else if (D+w < d[v]) {
                dp[0][v] = min(dp[0][u],dist[0][v]);
                dp[1][v] = min(dp[1][u],dist[1][v]);
                d[v] = D + w;
                pq.push(pii(d[v],v));
            }
        }
    }
    return dp[0][f] + dp[1][f];
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> S >> T >> U >> V;
    for (int i = 1; i <= m; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back(pii(v,w));
        adj[v].push_back(pii(u,w));
    }
    dijsktra1(0,U);
    dijsktra1(1,V);
    ll res = dist[0][V];
    res = min(res,dijsktra2(S,T));
    res = min(res,dijsktra2(T,S));
    cout << res;
    return 0;
}

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