提出 #7224908

ソースコード 拡げる

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#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;
}

提出情報

ジャッジ結果