#include <bits/stdc++.h>
using namespace std;
#define ll long
#define pii pair<int,long>
#define fr first
#define sc second
#define pow2(i) (1<<i)
#define eb emplace_back
#define mp make_pair
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define FOR(_i, _s, _n) for (int _i = _s; _i <= _n; ++_i)
#define FOD(_i, _s, _n) for (int _i = _s; _i >= _n; --_i)
#define firstbit(_mask) __builtin_ctz(_mask)
#define lastbit(_mask) __builtin_clz(_mask)
#define countbit(_mask) __builtin_popcount(_mask)
int getbit(int mask, int i) {
return (mask >> i) & 1;
}
void flipbit(int &mask, int i) {
mask ^= (1 << i);
}
void setbit(int &mask, int i) {
mask |= (1 << i);
}
template <typename T> inline void read(T &x) {
x = 0; char c;
while (!isdigit(c = getchar()));
do x = x*10 + c - '0';
while (isdigit(c = getchar()));
}
template <typename T> inline void write(T x) {
if (x > 9) write(x/10);
putchar(x % 10 + 48);
}
const int dd[4]={-1, 0, 1, 0}, dc[4]={0, 1, 0, -1};
//#define PROBLEMS "RELAYMARATHON"
#ifdef PROBLEMS
#define cin fi
#define cout fo
ifstream fi (PROBLEMS".inp");
ofstream fo (PROBLEMS".out");
#endif
#define camnguyenmeow ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
/* /\_/\
(= ._.)
/ >? \>$
*/
int n, m, k, firstnear[5001], secondnear[5001], a[5001];
ll d[100005], c[5001][5001];
bool sp[100005], vis[100005];
vector<pii> adj[100005];
int main()
{
camnguyenmeow;
cin >> n >> m >> k;
vector<pair<pii, int> > dsc(m);
int x, y;
ll z;
bool sub3 = true;
for (pair<pii, int> &i : dsc) {
cin >> i.fr.fr >> i.fr.sc >> i.sc;
if ((i.fr.fr == 1 && i.fr.sc != 2) || (i.fr.fr == 2 && i.fr.sc != 1) || (i.fr.fr != 1 && i.fr.sc == 2) || (i.fr.fr != 2 && i.fr.sc == 1)) sub3 = false;
if (((i.fr.fr == 1 && i.fr.sc == 2) || (i.fr.fr == 2 && i.fr.sc == 1)) && i.sc != 1) sub3 = false;
adj[i.fr.fr].push_back({i.fr.sc, i.sc}); adj[i.fr.sc].push_back({i.fr.fr, i.sc});
}
FOR(i, 1, k) {
cin >> a[i]; sp[a[i]] = true;
}
if (sub3) {
ll ans = LONG_MAX;
FOR(i, 3, k) {
priority_queue<pii, vector<pii>, greater<pii> > pq;
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
vis[1] = vis[2] = true;
d[a[i]] = 0;
pq.push({0, a[i]});
int cnt = 0;
while (!pq.empty()) {
int u = pq.top().sc; pq.pop();
if (vis[u]) continue;
vis[u] = true;
if (sp[u]) ++cnt;
if (d[u] > ans) break;
if (cnt == 2) {
ans = min(ans, d[u]);
break;
}
for (pii v : adj[u])
if (!vis[v.fr] && d[v.fr] > d[u] + v.sc) {
d[v.fr] = d[u] + v.sc;
pq.push({d[v.fr], v.fr});
}
}
}
cout << ans + 1;
return 0;
}
memset(c, 0x3f, sizeof(c));
for (pair<pii, int> i : dsc)
c[i.fr.fr][i.fr.sc] = c[i.fr.sc][i.fr.fr] = i.sc;
FOR(i, 1, n)
FOR(u, 1, n)
FOR(v, 1, n) {
c[u][v] = min(c[u][v], c[u][i] + c[i][v]);
if (sp[v] && sp[u] && v != u) {
if (c[u][firstnear[u]] > c[u][v]) {
secondnear[u] = firstnear[u];
firstnear[u] = v;
}
else if (v != firstnear[u] && c[u][secondnear[u]] > c[u][v])
secondnear[u] = v;
}
}
ll ans = LONG_MAX;
FOR(i, 1, k)
FOR(j, 1, k) {
if (i == j) continue;
int fn = firstnear[a[j]], sn = secondnear[a[j]];
FOR(z, 1, k) {
if (z == i || z == j) continue;
if (fn && fn != a[i] && fn != a[z])
ans = min(ans, c[a[i]][a[z]] + c[a[j]][fn]);
else if (sn && sn != a[i] && sn != a[z])
ans = min(ans, c[a[i]][a[z]] + c[a[j]][sn]);
}
}
cout << ans;
}
Compilation message
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:60:9: warning: unused variable 'x' [-Wunused-variable]
60 | int x, y;
| ^
RelayMarathon.cpp:60:12: warning: unused variable 'y' [-Wunused-variable]
60 | int x, y;
| ^
RelayMarathon.cpp:61:8: warning: unused variable 'z' [-Wunused-variable]
61 | ll z;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
198508 KB |
Output is correct |
| 2 |
Correct |
110 ms |
198636 KB |
Output is correct |
| 3 |
Correct |
108 ms |
198508 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
3584 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
198508 KB |
Output is correct |
| 2 |
Correct |
110 ms |
198636 KB |
Output is correct |
| 3 |
Correct |
108 ms |
198508 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
3584 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
10164 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4460 KB |
Output is correct |
| 3 |
Correct |
1782 ms |
212216 KB |
Output is correct |
| 4 |
Runtime error |
767 ms |
166932 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
198508 KB |
Output is correct |
| 2 |
Correct |
110 ms |
198636 KB |
Output is correct |
| 3 |
Correct |
108 ms |
198508 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
3584 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
