Submission #1124413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124413		South_Cloud	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	457 ms	24504 KiB

commuter_pass

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

const int N = 1e5;

int n, m, S, T, U, V;

long long d[2][N + 2], f[N + 2][3];

vector<pair<int, int> > adj[N + 2];

void input() {
    cin >> n >> m;
    cin >> S >> T;
    cin >> U >> V;
    int u, v, w;
    for(int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }
}

bool minimize(long long &x, long long y) {
    if(x > y) {
        x = y;
        return true;
    }
    return false;
}

void dijkstra(int x, int type) {
    priority_queue<pair<long long, int> > pq;
    memset(d[type], 0x3f, sizeof d[type]);
    d[type][x] = 0;
    pq.push(make_pair(0, x));
    while(pq.size()) {
        long long l = -pq.top().fi;
        int u = pq.top().se;
        pq.pop();
        if(d[type][u] != l) continue;
        for(pair<int, int> e : adj[u]) {
            int v = e.fi;
            int w = e.se;
            if(minimize(d[type][v], d[type][u] + w))
                pq.push(make_pair(-d[type][v], v));
        }
    }
}

void calc(int x) {
    priority_queue<pair<pair<long long, int>, int > > pq;
    memset(f, 0x3f, sizeof f);
    f[x][0] = 0;
    pq.push(make_pair(make_pair(0, 0), x));
    while(pq.size()) {
        long long l = -pq.top().fi.fi;
        int type = pq.top().fi.se;
        int u = pq.top().se;
        pq.pop();
        if(f[u][type] != l) continue;
        for(pair<int, int> e : adj[u]) {
            int v = e.fi;
            int w = e.se;
            if(d[0][u] + w + d[1][v] == d[0][T] && type != 2) {
                if(minimize(f[v][1], f[u][type]))
                    pq.push(make_pair(make_pair(-f[v][1], 1), v));
            }
            if(type != 1) {
                if(minimize(f[v][type], f[u][type] + w))
                    pq.push(make_pair(make_pair(-f[v][type], type), v));
            } else if(minimize(f[v][2], f[u][type] + w))
                    pq.push(make_pair(make_pair(-f[v][2], 2), v));
        }
    }
}

void solve() {
    dijkstra(S, 0);
    dijkstra(T, 1);
    calc(U);
    long long res = min({f[V][0], f[V][1], f[V][2]});
    calc(V);
    cout << min({res, f[U][0], f[U][1], f[U][2]});
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    input();
    solve();
    return 0;
}

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