// BEGIN BOILERPLATE CODE
#include <bits/stdc++.h>
using namespace std;
#ifdef KAMIRULEZ
const bool kami_loc = true;
const long long kami_seed = 69420;
#else
const bool kami_loc = false;
const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif
const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);
long long rand_range(long long rmin, long long rmax) {
uniform_int_distribution<long long> rdist(rmin, rmax);
return rdist(kami_gen);
}
long double rand_real(long double rmin, long double rmax) {
uniform_real_distribution<long double> rdist(rmin, rmax);
return rdist(kami_gen);
}
void file_io(string fi, string fo) {
if (fi != "" && (!kami_loc || fi == kami_fi)) {
freopen(fi.c_str(), "r", stdin);
}
if (fo != "" && (!kami_loc || fo == kami_fo)) {
freopen(fo.c_str(), "w", stdout);
}
}
void set_up() {
if (kami_loc) {
file_io(kami_fi, kami_fo);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
}
void just_do_it();
void just_exec_it() {
if (kami_loc) {
auto pstart = chrono::steady_clock::now();
just_do_it();
auto pend = chrono::steady_clock::now();
long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
string bar(50, '=');
cout << '\n' << bar << '\n';
cout << "Time: " << ptime << " ms" << '\n';
}
else {
just_do_it();
}
}
int main() {
set_up();
just_exec_it();
return 0;
}
// END BOILERPLATE CODE
// BEGIN MAIN CODE
const int ms = 1e5 + 20;
const int inf = 1e9 + 20;
vector<pair<int, int>> adj[ms];
int ds[ms];
int du[ms];
int dv[ms];
int h[ms];
int g[ms];
bool f[ms];
int n;
void dijk(int d[]) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for (int i = 1; i <= n; i++) {
if (d[i] == 0) {
h[i] = i;
q.push({0, i});
}
}
while (!q.empty()) {
int cd = q.top().first;
int u = q.top().second;
q.pop();
if (d[u] != cd) {
continue;
}
for (auto x: adj[u]) {
int v = x.first;
if (f[v]) {
continue;
}
int w = x.second;
if (d[u] + w < d[v]) {
d[v] = d[u] + w;
h[v] = h[u];
q.push({d[v], v});
}
}
}
}
bool cmp(int u, int v) {
return dv[u] < dv[v];
}
void just_do_it() {
//file_io("4special.inp", "4special.out");
int m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
ds[i] = inf;
du[i] = inf;
dv[i] = inf;
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 0; i < k; i++) {
int u;
cin >> u;
g[i] = u;
ds[u] = 0;
}
dijk(ds);
int mi = inf;
int fu = -1;
int fv = -1;
for (int i = 1; i <= n; i++) {
for (auto x: adj[i]) {
int j = x.first;
int w = x.second;
if (h[i] != h[j]) {
if (ds[i] + ds[j] + w < mi) {
mi = ds[i] + ds[j] + w;
fu = h[i];
fv = h[j];
}
}
}
}
du[fu] = 0;
dijk(du);
dv[fv] = 0;
dijk(dv);
sort(g, g + k, cmp);
int res = inf;
for (int i = 0; i < k; i++) {
if (g[i] == fu || g[i] == fv) {
continue;
}
for (int j = 0; j < k; j++) {
if (g[j] != g[i] && g[j] != fu && g[j] != fv) {
res = min(res, mi + du[g[i]] + dv[g[j]]);
break;
}
}
}
for (int i = 1; i <= n; i++) {
ds[i] = inf;
}
for (int i = 0; i < k; i++) {
ds[g[i]] = 0;
}
ds[fu] = inf;
ds[fv] = inf;
f[fu] = true;
f[fv] = true;
dijk(ds);
for (int i = 1; i <= n; i++) {
for (auto x: adj[i]) {
int j = x.first;
int w = x.second;
if (h[i] != h[j]) {
res = min(res, mi + ds[i] + ds[j] + w);
}
}
}
cout << res;
}
// END MAIN CODE
Compilation message
RelayMarathon.cpp: In function 'void file_io(std::string, std::string)':
RelayMarathon.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | freopen(fi.c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | freopen(fo.c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
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 |
53 ms |
8052 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4548 KB |
Output is correct |
| 3 |
Correct |
1292 ms |
85272 KB |
Output is correct |
| 4 |
Correct |
558 ms |
48472 KB |
Output is correct |
| 5 |
Correct |
145 ms |
13232 KB |
Output is correct |
| 6 |
Correct |
131 ms |
11224 KB |
Output is correct |
| 7 |
Correct |
156 ms |
14156 KB |
Output is correct |
| 8 |
Correct |
70 ms |
8128 KB |
Output is correct |
| 9 |
Correct |
99 ms |
10616 KB |
Output is correct |
| 10 |
Correct |
81 ms |
8928 KB |
Output is correct |
| 11 |
Correct |
1296 ms |
89812 KB |
Output is correct |
| 12 |
Correct |
83 ms |
9296 KB |
Output is correct |
| 13 |
Correct |
349 ms |
31400 KB |
Output is correct |
| 14 |
Correct |
165 ms |
14300 KB |
Output is correct |
| 15 |
Correct |
1246 ms |
88216 KB |
Output is correct |
| 16 |
Correct |
55 ms |
7644 KB |
Output is correct |
| 17 |
Correct |
859 ms |
75228 KB |
Output is correct |
| 18 |
Correct |
9 ms |
4692 KB |
Output is correct |
| 19 |
Correct |
1408 ms |
94412 KB |
Output is correct |
| 20 |
Correct |
152 ms |
13640 KB |
Output is correct |
| 21 |
Correct |
151 ms |
12568 KB |
Output is correct |
| 22 |
Correct |
75 ms |
8780 KB |
Output is correct |
| 23 |
Correct |
20 ms |
6692 KB |
Output is correct |
| 24 |
Correct |
942 ms |
82656 KB |
Output is correct |
| 25 |
Correct |
107 ms |
10816 KB |
Output is correct |
| 26 |
Correct |
54 ms |
8128 KB |
Output is correct |
| 27 |
Correct |
106 ms |
9688 KB |
Output is correct |
| 28 |
Correct |
12 ms |
5716 KB |
Output is correct |
| 29 |
Correct |
162 ms |
13916 KB |
Output is correct |
| 30 |
Correct |
348 ms |
24436 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 |
- |
