#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#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 ALL(x) (x).begin(), (x).end()
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define ii pair <int, int>
#define fi first
#define se second
using namespace std;
const int MAXN = 1e5 + 5;
const int INF = 1e9 + 7;
int N, M, K;
vector <ii> ke[MAXN];
vector <int> Special;
struct SUB2{
int dist[505], C[505][505];
vector <vector <ii>> Dist;
void Dijsktra(int id) {
FOR(i, 1, N) dist[i] = INF;
priority_queue <ii, vector <ii>, greater <ii>> q;
q.emplace(dist[Special[id]] = 0, Special[id]);
while (q.size()) {
int du = q.top().fi, u = q.top().se; q.pop();
if (du != dist[u]) continue;
for (ii x : ke[u]) {
int v = x.fi, w = x.se;
if (dist[v] > du + w) {
dist[v] = du + w;
q.emplace(du + w, v);
}
}
}
FOR(i, 1, N) C[id][i] = dist[i];
for (int x : Special) if (x != Special[id])
Dist[id].emplace_back(dist[x], x);
}
void solve() {
if (N > 500) return;
Dist.resize(K);
REP(i, K) Dijsktra(i);
int ans = INF;
REP(i, K) REP(j, K) if (i != j && C[i][Special[j]] != INF)
REP(t, K) if (i != t && j != t) {
int tmp = C[i][Special[j]];
for (ii x : Dist[t]) if (x.se != Special[i] && x.se != Special[j]) {
tmp += x.fi;
break;
}
ans = min(ans, tmp);
}
cout << ans;
exit(0);
}
}sub2;
struct SUB3{
bool dd[MAXN];
vector <int> Gate;
ii ans[MAXN];
int dist[MAXN], trace[MAXN];
void Dijsktra(int k, int c) {
priority_queue <ii, vector <ii>, greater <ii>> q;
FOR(i, 1, N) dist[i] = 1e18, trace[i] = 0;
for (auto x : Gate) if (((x >> k) & 1) == c)
q.emplace(dist[x] = 0, x), trace[x] = x;
while (q.size()) {
long long du = q.top().fi;
int u = q.top().se;
q.pop();
if (du != dist[u]) continue;
for (auto x : ke[u]) {
int v = x.fi, w = x.se;
if (dist[v] > du + w) {
dist[v] = du + w;
trace[v] = trace[u];
q.emplace(du + w, v);
} else if (dist[v] == du + w) {
if (trace[v] > trace[u]) {
trace[v] = trace[u];
q.emplace(du + w, v);
}
}
}
}
for (auto x : Gate) if (((x >> k) & 1) != c)
ans[x] = min(ans[x], {dist[x], trace[x]});
}
void solve() {
bool ok = 0;
for (int x : Special) dd[x] = 1;
for (int x : Special)
if (ke[x].size() == 1 && dd[ke[x][0].fi] && ke[x][0].se == 1) {
if (ke[ke[x][0].fi].size() != 1) continue;
dd[x] = dd[ke[x][0].fi] = 0;
ok = 1;
break;
}
if (!ok) return;
for (int x : Special) if (dd[x]) Gate.emplace_back(x);
for (int x : Gate) ans[x] = {INF, -1};
FOD(i, 18, 0) REP(c, 2)
Dijsktra(i, c);
int res = INF;
for (int x : Gate) res = min(res, ans[x].fi);
cout << res + 1; exit(0);
}
}sub3;
signed main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//file("TASK");
cin >> N >> M >> K;
while (M--) {
int u, v, w; cin >> u >> v >> w;
ke[u].emplace_back(v, w);
ke[v].emplace_back(u, w);
}
Special.resize(K);
for (int &x : Special) cin >> x;
sub2.solve();
sub3.solve();
cerr << "Time elapsed: " << TIME << " s.\n";
return (0 ^ 0);
}
Compilation message
RelayMarathon.cpp: In member function 'void SUB3::Dijsktra(int, int)':
RelayMarathon.cpp:71:32: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
71 | FOR(i, 1, N) dist[i] = 1e18, trace[i] = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
8264 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4888 KB |
Output is correct |
| 3 |
Correct |
3830 ms |
68220 KB |
Output is correct |
| 4 |
Correct |
2707 ms |
43340 KB |
Output is correct |
| 5 |
Correct |
1139 ms |
13408 KB |
Output is correct |
| 6 |
Correct |
896 ms |
11436 KB |
Output is correct |
| 7 |
Correct |
1298 ms |
14276 KB |
Output is correct |
| 8 |
Correct |
405 ms |
8296 KB |
Output is correct |
| 9 |
Correct |
827 ms |
10708 KB |
Output is correct |
| 10 |
Correct |
582 ms |
9096 KB |
Output is correct |
| 11 |
Correct |
4163 ms |
70496 KB |
Output is correct |
| 12 |
Correct |
716 ms |
9660 KB |
Output is correct |
| 13 |
Correct |
2013 ms |
33244 KB |
Output is correct |
| 14 |
Correct |
1252 ms |
14852 KB |
Output is correct |
| 15 |
Correct |
3932 ms |
69612 KB |
Output is correct |
| 16 |
Correct |
224 ms |
7712 KB |
Output is correct |
| 17 |
Correct |
3481 ms |
51932 KB |
Output is correct |
| 18 |
Correct |
8 ms |
4940 KB |
Output is correct |
| 19 |
Correct |
4538 ms |
73632 KB |
Output is correct |
| 20 |
Correct |
1203 ms |
13820 KB |
Output is correct |
| 21 |
Correct |
1073 ms |
12744 KB |
Output is correct |
| 22 |
Correct |
504 ms |
8904 KB |
Output is correct |
| 23 |
Correct |
26 ms |
6868 KB |
Output is correct |
| 24 |
Correct |
3114 ms |
58336 KB |
Output is correct |
| 25 |
Correct |
848 ms |
10864 KB |
Output is correct |
| 26 |
Correct |
390 ms |
8380 KB |
Output is correct |
| 27 |
Correct |
716 ms |
9856 KB |
Output is correct |
| 28 |
Correct |
14 ms |
5844 KB |
Output is correct |
| 29 |
Correct |
1209 ms |
14024 KB |
Output is correct |
| 30 |
Correct |
1908 ms |
24788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
