제출 #1087591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087591		pqthangv	Commuter Pass (JOI18_commuter_pass)	C++11	0 / 100	38 ms	23892 KiB

commuter_pass

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

#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define pb push_back
#define fi first
#define se second
#define el '\n'
#define ll long long
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))

const int maxN = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e18;

struct Edges {
    int u, v;
    ll cost;

    Edges(int _u = 0, int _v = 0, ll _c = 0) : u(_u), v(_v), cost(_c) {}
} b[maxN];

int n, m, s, t, u, v;
vector< pair <int, ll> > adj[maxN];
vector < int > g[maxN];
ll dist[5][maxN], fu[maxN], fv[maxN], ans;
bool vis[maxN];

void dijk(int start, int type) {
    priority_queue< pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> > > pq;
    FOR(i, 1, n) dist[type][i] = INF;

    dist[type][start] = 0;
    pq.push(make_pair(0, start));
    while(!pq.empty()) {
        int u = pq.top().se;
        ll cost = pq.top().fi;
        pq.pop();

        if (cost > dist[type][u]) continue;
        for(pair <int, ll> s : adj[u]) {
            int v = s.fi;
            ll cost = s.se;
            if (dist[type][v] > dist[type][u] + cost) {
                dist[type][v] = dist[type][u] + cost;
                pq.push(make_pair(dist[type][v], v));
            }
        }
    }
}

void dfs(int start) {
    fu[start] = dist[3][start];
    fv[start] = dist[4][start];
    vis[start] = 1;

    for(int child : g[start]) {
        if (vis[child] == false) {
            dfs(child);
        }
        fu[start] = min(fu[start], fu[child]);
        fv[start] = min(fv[start], fv[child]);
    }

    // cout << start << " " << dist[3][start] + fv[start] << " " << dist[4][start] + fu[start] << el;

    ans = min(ans, dist[3][start] + fv[start]);
    ans = min(ans, dist[4][start] + fu[start]);
}

void etoile() {
    cin >> n >> m >> s >> t >> u >> v;
    FOR(i, 1, m) {
        int u, v;
        ll c;
        cin >> u >> v >> c;
        adj[u].pb(make_pair(v, c));
        adj[v].pb(make_pair(u, c));
        b[i] = Edges(u, v, c);
    }

    dijk(s, 1);
    dijk(t, 2);
    dijk(u, 3);
    dijk(v, 4);

    // build dag
    FOR(i, 1, m) {
        int u = b[i].u;
        int v = b[i].v;
        ll c = b[i].cost;

        if (dist[1][u] + dist[2][v] + c == dist[1][t]) {
            g[u].pb(v);
            // cout << u << " " << v << el;
        }
    }
    // cout << el;

    ans = dist[3][v];
//    FOR(i, 1, 4) {
//        FOR(j, 1, n) {
//            cout << dist[i][j] << el;
//        }
//        cout << el;
//    }
    dfs(s);
    cout << ans << el;
}

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

    /* #define cecilia "bus"
    freopen(cecilia".inp", "r", stdin);
    freopen(cecilia".out", "w", stdout); */

    etoile();
    return 0;
}
/*
5 6
1 3
4 5
1 2 10
1 3 30
1 4 15
2 3 10
4 3 5
3 5 10

*/

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