Contest Duration: ~ (local time) (300 minutes) Back to Home

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);
if (from_s1[t1] != LLONG_MAX and from_s2[t2] != LLONG_MAX) {;
REP (i, n) if (from[i] != LLONG_MAX and to[i] != LLONG_MAX) {
}
}

// output
cout << "Impossible" << endl;
} else {
}
return 0;
}
```

#### Submission Info

Submission Time 2019-08-31 18:14:39+0900 F - Road Construction kimiyuki C++14 (GCC 5.4.1) 100 3095 Byte AC 471 ms 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