Submission #854793

#	Time	Username	Problem	Language	Result	Execution time	Memory
854793		hungnt	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2040 ms	17356 KiB

commuter_pass

#include<bits/stdc++.h>
#define ft first
#define sc second
#define ll long long
#define all(x) x.begin(),x.end()
#define bit(x, i) ((x >> i)&1)
#define pii pair<int, int>
using namespace std;

const int N = 1e5 + 2;

vector<pii> ad[N];

#define plli pair<ll,int>
long long f[6][N];
int tt[N], n, m, TR[6][N];

const ll INF = (ll)1e18 + 7;

void dijkstra(int s) {
    int d = tt[s];
    priority_queue<plli, vector<plli>, less<plli> > pq;
    for (int i = 1; i <= n; i++) {
        f[d][i] = INF;
    }
    f[d][s] = 0;
    pq.push({f[d][s], s});
    while (pq.size()) {
        long long value = pq.top().ft;
        int numb = pq.top().sc;
        pq.pop();
        if (value != f[d][numb]) continue;
        for (pii u : ad[numb]) {
            if (value + 1ll * u.sc < f[d][u.ft]) {
                f[d][u.ft] = value + 1ll * u.sc;
                TR[d][u.ft] = numb;
                pq.push({f[d][u.ft], u.ft});
            }
        }
    }
}


int s, t, u, v;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

//    freopen("in.inp", "r", stdin);
  
    cin >> n >> m;
    cin >> s >> t >> u >> v;
    tt[s] = 1; tt[t] = 2; tt[u] = 3; tt[v] = 4;
    int a, b, c;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        ad[a].push_back({b, c});
        ad[b].push_back({a, c});
    }
    dijkstra(s);
    dijkstra(u);
    dijkstra(v);
    vector<int> check(n + 1, 0);
    int p = t;
    check[s] = check[t] = 1;
    long long resu = INF, resv = INF;
    while (p != s) {
        check[p] = 1;
        resu = min(resu, f[tt[u]][p]);
        resv = min(resv, f[tt[v]][p]);
        p = TR[tt[s]][p];
    }
    resu = min(resu, f[tt[u]][s]);
    resv = min(resv, f[tt[v]][s]);
    if (u == v) cout << 0;
    else {
        cout << min(f[tt[u]][v], resu + resv);
    }
}

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