/**
* NAME : PHAM VAN SAM
* DATE : 12.01.2023 08:03:57
* ┌───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
* │Esc│ │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│ ┌┐ ┌┐ ┌┐
* └───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘ └┘ └┘ └┘
* ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
* ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │ │
* ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter │ │ 4 │ 5 │ 6 │ │
* ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤ ┌───┐ ├───┼───┼───┼───┤
* │ Shift │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│ Shift │ │ ↑ │ │ 1 │ 2 │ 3 │ │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ Win│ Alt│ Space │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │ 0 │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
**/
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define int long long
#define MASK(x) (1LL << (x))
#define BIT(x, k) (((x) >> (k)) & 1LL)
#define all(x) (x).begin(),(x).end()
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define Fod(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Fore(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
template <class U, class V> bool maximize(U &A, const V &B){ return (A < B) ? (A = B, true) : false;}
template <class U, class V> bool minimize(U &A, const V &B){ return (A > B) ? (A = B, true) : false;}
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }
const int MAXN = 1e5 + 5;
int N, M, K, d[MAXN];
vector <pair <int, int>> ke[MAXN];
vector <int> special;
bool dd[MAXN];
namespace sub1 {
int dp[55][55];
void dijkstra (int u) {
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
fill(dp[u] + 1, dp[u] + N + 1, 2e9);
dp[u][u] = 0;
heap.push(make_pair(dp[u][u], u));
while(heap.size()) {
int x = heap.top().second;
int w1 = heap.top().first;
heap.pop();
if(dp[u][x] != w1) continue;
for (auto [v, w] : ke[x]) if(minimize(dp[u][v], dp[u][x] + w)) {
heap.push(make_pair(dp[u][v], v));
}
}
}
void Main() {
int ans = 2e9;
for (auto u : special) dijkstra(u);
rep (i, (int) special.size()) {
rep (j, (int) special.size()) {
For (u, i + 1, (int) special.size() - 1) {
if(dp[special[i]][special[u]] == 2e9) continue;
For (v, j + 1, (int) special.size() - 1){
if(dp[special[j]][special[v]] == 2e9) continue;
if(i != v && i != j && u != j && u != v) {
minimize(ans, dp[special[i]][special[u]] + dp[special[j]][special[v]]);
}
}
}
}
}
cout << ans << '\n';
}
}
namespace LieuAnNhieu{
int trace[MAXN];
struct SegmentTree {
vector <int> it;
SegmentTree() = default;
SegmentTree(int n) : it(4 * n + 5, 2e9) {}
void update(int idx, int l, int r, int u, int x) {
if(l > u || r < u) return;
if(l == r) return void(minimize(it[idx], x));
int mid = (l + r) >> 1;
update(idx << 1, l, mid, u, x);
update(idx << 1 | 1, mid + 1, r, u, x);
it[idx] = min(it[idx << 1], it[idx << 1 | 1]);
}
int get(int idx, int l, int r, int u, int v) {
if(l > v || r < u) return 2e9;
if(l >= u && r <= v) return it[idx];
int mid = (l + r) >> 1;
return min(get(idx << 1, l, mid, u, v), get(idx << 1 | 1, mid + 1, r, u, v));
}
};
struct Data {
int u, v, w;
Data(int u, int v, int w) {
this-> u = u;
this-> v = v;
this-> w = w;
}
friend bool operator < (const Data &A, const Data &B) {
return (A.w < B.w || (A.w == B.w && A.u < B.u));
}
friend bool operator == (const Data &A, const Data &B) {
return (A.w == B.w && A.u == B.u && A.v == B.v);
}
};
vector <Data> val;
void dijkstra(int bit, int type) {
fill(d + 1, d + N + 1, 1e9);
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
for (auto x : special) if(BIT(x, bit) == type) {
d[x] = 0;
trace[x] = x;
heap.push(make_pair(0, x));
}
while(heap.size()) {
int u = heap.top().second;
int w1 = heap.top().first;
heap.pop();
if(d[u] != w1) continue;
for (auto [v, w] : ke[u]) if(minimize(d[v], d[u] + w)) {
heap.push(make_pair(d[v], v));
trace[v] = trace[u];
}
}
for (auto x : special) {
if(BIT(x, bit) == type || d[x] == 1e9) continue;
val.push_back(Data(min(x, trace[x]), max(x, trace[x]), d[x]));
}
sort (val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
while(val.size() > K) val.pop_back();
}
void lieu_thi_an_nhieu() {
For (i, 0, 16) {
dijkstra(i, 0);
dijkstra(i, 1);
}
// return;
SegmentTree IT(N);
int ans = 2e9;
int j = 0;
sort (val.begin(), val.end(), [](Data A, Data B) {
return A.u < B.u;
});
For (i, 0, (int) val.size()) {
while(j < i && val[j].u < val[i].u) {
IT.update(1, 1, N, val[j].v, val[j].w);
j++;
}
minimize(ans, val[i].w + min({IT.get(1, 1, N, 1, val[i].u - 1),
IT.get(1, 1, N, val[i].u + 1, val[i].v - 1),
IT.get(1, 1, N, val[i].v + 1, N)}));
}
cout << ans << '\n';
}
}
namespace sub3 {
int dp[MAXN], trace[MAXN];
priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
void dijkstra() {
fill (dp + 1, dp + N + 1, 2e9);
for (auto x : special) {
if(x == x1 || x == x2) continue;
dp[x] = 0; trace[x] = x;
heap.push(make_pair(0, x));
}
while(heap.size()) {
int u = heap.top().second;
int w1 = heap.top().first;
heap.pop();
if(dp[u] != w1) continue;
for (auto [v, w] : ke[u]) if(minimize(dp[v], dp[u] + w)) {
heap.push(make_pair(dp[v], v));
trace[v] = trace[u];
}
}
}
void Main() {
dijkstra();
int Min1 = 2e9;
For (u, 1, N) {
for (auto [v, w] : ke[u]) {
if(trace[u] == trace[v]) continue;
if(minimize(Min1, dp[u] + dp[v] + w)) {
x1 = trace[u]; x2 = trace[v];
}
}
}
// cout << x1 << " " << x2 << " " << Min1 << '\n';
int Min2 = 2e9;
dijkstra();
For (u, 1, N) {
for (auto [v, w] : ke[u]) {
if(trace[u] == trace[v]) continue;
if(x1 != trace[u] && x2 != trace[u] && x1 != trace[v] && x2 != trace[v]) {
if(minimize(Min2, dp[u] + dp[v] + w)) y1 = trace[u], y2 = trace[v];
}
}
}
// cout << y1 << " " << y2 << " " << Min2 << '\n';
cout << Min1 + Min2;
}
}
void solve(void) {
cin >> N >> M >> K;
while(M--) {
int u, v, w; cin >> u >> v >> w;
ke[u].push_back(make_pair(v, w));
ke[v].push_back(make_pair(u, w));
}
For (i, 1, K) {
int x; cin >> x; special.push_back(x);
}
/*if(N <= 50) sub1::Main();
else if(N <= 500) LieuAnNhieu::lieu_thi_an_nhieu();
else*/ sub3::Main();
}
signed main() {
// file("4SPECIAL");
file("TASK");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int test; test = 1;
// cin >> test;
while(test--) {
solve();
cout << '\n';
}
// cerr << "Time elapsed: " << TIME << " s.\n";
return (0 ^ 0);
}
Compilation message
RelayMarathon.cpp: In function 'void LieuAnNhieu::dijkstra(long long int, long long int)':
RelayMarathon.cpp:141:26: warning: comparison of integer expressions of different signedness: 'std::vector<LieuAnNhieu::Data>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
141 | while(val.size() > K) val.pop_back();
| ~~~~~~~~~~~^~~
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:31:56: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:232:5: note: in expansion of macro 'file'
232 | file("TASK");
| ^~~~
RelayMarathon.cpp:31:89: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:232:5: note: in expansion of macro 'file'
232 | file("TASK");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
8060 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4072 KB |
Output is correct |
| 3 |
Correct |
1227 ms |
120108 KB |
Output is correct |
| 4 |
Correct |
552 ms |
59004 KB |
Output is correct |
| 5 |
Correct |
153 ms |
14276 KB |
Output is correct |
| 6 |
Correct |
125 ms |
11756 KB |
Output is correct |
| 7 |
Correct |
170 ms |
15424 KB |
Output is correct |
| 8 |
Correct |
55 ms |
8272 KB |
Output is correct |
| 9 |
Correct |
104 ms |
11148 KB |
Output is correct |
| 10 |
Correct |
73 ms |
9208 KB |
Output is correct |
| 11 |
Correct |
1259 ms |
126692 KB |
Output is correct |
| 12 |
Correct |
85 ms |
9716 KB |
Output is correct |
| 13 |
Correct |
357 ms |
36252 KB |
Output is correct |
| 14 |
Correct |
185 ms |
15556 KB |
Output is correct |
| 15 |
Correct |
1208 ms |
124532 KB |
Output is correct |
| 16 |
Correct |
39 ms |
7496 KB |
Output is correct |
| 17 |
Correct |
882 ms |
92300 KB |
Output is correct |
| 18 |
Correct |
6 ms |
4180 KB |
Output is correct |
| 19 |
Correct |
1462 ms |
133124 KB |
Output is correct |
| 20 |
Correct |
195 ms |
14744 KB |
Output is correct |
| 21 |
Correct |
193 ms |
13712 KB |
Output is correct |
| 22 |
Correct |
76 ms |
9084 KB |
Output is correct |
| 23 |
Correct |
23 ms |
6484 KB |
Output is correct |
| 24 |
Correct |
919 ms |
102736 KB |
Output is correct |
| 25 |
Correct |
109 ms |
11296 KB |
Output is correct |
| 26 |
Correct |
64 ms |
8272 KB |
Output is correct |
| 27 |
Correct |
88 ms |
10160 KB |
Output is correct |
| 28 |
Correct |
15 ms |
5332 KB |
Output is correct |
| 29 |
Correct |
170 ms |
15112 KB |
Output is correct |
| 30 |
Correct |
321 ms |
28588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
