Submission #7224908


Source Code Expand

Copy
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T, class U> inline void chmin(T & a, U const & b) { a = min<T>(a, b); }

/**
 * @note O((E + V) log V)
 */
vector<ll> dijkstra(vector<vector<pair<int, ll> > > const & g, int root) {
    vector<ll> dist(g.size(), LLONG_MAX);
    priority_queue<pair<ll, int> > que;
    dist[root] = 0;
    que.emplace(- dist[root], root);
    while (not que.empty()) {
        ll dist_i; int i; tie(dist_i, i) = que.top(); que.pop();
        if (dist[i] < - dist_i) continue;
        for (auto it : g[i]) {
            int j; ll cost; tie(j, cost) = it;
            if (- dist_i + cost < dist[j]) {
                dist[j] = - dist_i + cost;
                que.emplace(dist_i - cost, j);
            }
        }
    }
    return dist;
}

/**
 * @description find the cost to connect edges from x1 and x2 to y
 */
vector<ll> dijkstra_two_nodes(vector<vector<pair<int, ll> > > const & g, int root1, int root2) {
    vector<ll> dist1 = dijkstra(g, root1);
    vector<ll> dist2 = dijkstra(g, root2);
    vector<ll> dist(g.size(), LLONG_MAX);
    priority_queue<pair<ll, int> > que;
    REP (i, g.size()) if (dist1[i] != LLONG_MAX and dist2[i] != LLONG_MAX) {
        dist[i] = dist1[i] + dist2[i];
        que.emplace(- dist[i], i);
    }
    while (not que.empty()) {
        ll dist_i; int i; tie(dist_i, i) = que.top(); que.pop();
        if (dist[i] < - dist_i) continue;
        for (auto it : g[i]) {
            int j; ll cost; tie(j, cost) = it;
            if (- dist_i + cost < dist[j]) {
                dist[j] = - dist_i + cost;
                que.emplace(dist_i - cost, j);
            }
        }
    }
    return dist;
}

int main() {
    // input
    int n, m; cin >> n >> m;
    int s1, t1, s2, t2; cin >> s1 >> t1 >> s2 >> t2;
    -- s1;
    -- t1;
    -- s2;
    -- t2;
    vector<vector<pair<int, ll> > > g(n);
    vector<vector<pair<int, ll> > > g_inv(n);
    REP (i, m) {
        ll cost; int s, t; cin >> cost >> s >> t;
        -- s;
        -- t;
        g[s].emplace_back(t, cost);
        g_inv[t].emplace_back(s, cost);
    }

    // solve
    auto from_s1 = dijkstra(g, s1);
    auto from_s2 = dijkstra(g, s2);
    auto to_t1 = dijkstra(g_inv, t1);
    auto to_t2 = dijkstra(g_inv, t2);
    auto from = dijkstra_two_nodes(g, s1, s2);
    auto to = dijkstra_two_nodes(g_inv, t1, t2);
    ll answer = LLONG_MAX;
    if (from_s1[t1] != LLONG_MAX and from_s2[t2] != LLONG_MAX) {;
        chmin(answer, from_s1[t1] + from_s2[t2]);
        REP (i, n) if (from[i] != LLONG_MAX and to[i] != LLONG_MAX) {
            chmin(answer, from[i] + to[i]);
        }
    }

    // output
    if (answer == LLONG_MAX) {
        cout << "Impossible" << endl;
    } else {
        cout << answer << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task F - Road Construction
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 100
Code Size 3095 Byte
Status
Exec Time 471 ms
Memory 27048 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_sample_01, 00_sample_02, 00_sample_03
All 100 / 100 00_sample_01, 00_sample_02, 00_sample_03, 01_small_01, 01_small_02, 01_small_03, 01_small_04, 01_small_05, 02_random_01, 02_random_02, 02_random_03, 02_random_04, 02_random_05, 02_random_06, 02_random_07, 02_random_08, 02_random_09, 02_random_10, 03_special_01, 03_special_02, 10_random_01, 10_random_02, 10_random_03, 10_random_04, 10_random_05, 10_random_06, 10_random_07, 10_random_08, 10_random_09, 10_random_10, 10_random_11, 10_random_12, 10_random_13, 10_random_14, 10_random_15
Case Name Status Exec Time Memory
00_sample_01 1 ms 256 KB
00_sample_02 1 ms 256 KB
00_sample_03 1 ms 256 KB
01_small_01 1 ms 256 KB
01_small_02 1 ms 256 KB
01_small_03 1 ms 256 KB
01_small_04 1 ms 256 KB
01_small_05 1 ms 256 KB
02_random_01 225 ms 17480 KB
02_random_02 226 ms 18536 KB
02_random_03 215 ms 12764 KB
02_random_04 294 ms 15180 KB
02_random_05 461 ms 23092 KB
02_random_06 193 ms 9496 KB
02_random_07 393 ms 22608 KB
02_random_08 106 ms 6924 KB
02_random_09 412 ms 23264 KB
02_random_10 335 ms 14532 KB
03_special_01 471 ms 27048 KB
03_special_02 311 ms 14900 KB
10_random_01 89 ms 6904 KB
10_random_02 73 ms 9928 KB
10_random_03 116 ms 6400 KB
10_random_04 134 ms 13256 KB
10_random_05 233 ms 16264 KB
10_random_06 164 ms 11696 KB
10_random_07 206 ms 18120 KB
10_random_08 196 ms 17672 KB
10_random_09 168 ms 9080 KB
10_random_10 55 ms 12072 KB
10_random_11 188 ms 15944 KB
10_random_12 185 ms 10392 KB
10_random_13 247 ms 15960 KB
10_random_14 217 ms 17440 KB
10_random_15 94 ms 9816 KB