Submission #502913

#	Time	Username	Problem	Language	Result	Execution time	Memory
502913		Lobo	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	373 ms	28448 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 220000

int n, m, d[maxn];
int ds[maxn], dt[maxn], du[maxn], dv[maxn];
pair<int,int> d1[maxn];
vector<pair<int,int>> g[maxn];

void sph(int beg) {
    for(int i = 1; i <= n; i++) {
        d[i] = inf;
    }

    d[beg] = 0;
    priority_queue<pair<int,int>> pq; pq.push(mp(0,beg));

    while(pq.size()) {
        int u = pq.top().sc;
        int dist = -pq.top().fr;
        pq.pop();

        if(dist != d[u]) continue;

        for(auto V : g[u]) {
            int v = V.fr;
            int w = V.sc;

            if(d[v] > d[u]+w) {
                d[v] = d[u]+w;
                pq.push(mp(-d[v],v));
            }
        }
    }
}

void sph1(int beg) {
    for(int i = 1; i <= n; i++) {
        d[i] = inf;
        d1[i] = mp(du[i],dv[i]);
    }

    d[beg] = 0;

    priority_queue<pair<int,int>> pq; pq.push(mp(0,beg));

    while(pq.size()) {
        int u = pq.top().sc;
        int dist = -pq.top().fr;
        pq.pop();

        if(dist != d[u]) continue;

        for(auto V : g[u]) {
            int v = V.fr;
            int w = V.sc;

            if(d[v] > d[u]+w) {
                d[v] = d[u]+w;
                d1[v].fr = min(d1[u].fr,du[v]);
                d1[v].sc = min(d1[u].sc,dv[v]);

                pq.push(mp(-d[v],v));
            }
            else if(d[v] == d[u]+w) {
                d1[v].fr = min(d1[u].fr,d1[v].fr);
                d1[v].sc = min(d1[u].sc,d1[v].sc);
            }
        }
    }
}

void solve() {
    int S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;

    for(int i = 0; i < m; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        g[a].pb(mp(b,c));
        g[b].pb(mp(a,c));
    }

    sph(U);
    for(int i = 1; i <= n; i++) {
        du[i] = d[i];
    }
    sph(V);
    for(int i = 1; i <= n; i++) {
        dv[i] = d[i];
    }
    sph(S);
    for(int i = 1; i <= n; i++) {
        ds[i] = d[i];
    }
    sph(T);
    for(int i = 1; i <= n; i++) {
        dt[i] = d[i];
    }

    sph1(S);

    int ans = du[V];
    for(int u = 1; u <= n; u++) {
        for(auto V : g[u]) {
            int v = V.fr;
            int w = V.sc;

            if(ds[u] + w + dt[v] == ds[T] || dt[u] + w + ds[v] == dt[S]) {
                ans = min(ans, d1[u].fr + dv[u]);
                ans = min(ans, du[u] + d1[u].sc);
            }

        }
    }

    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);


    int tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

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