#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define file "4special"
using namespace std;
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
return l + rd() % (r - l + 1);
}
const int N = 1e6 + 5;
const int mod = 1e9 + 7; // 998244353;
const int inf = INT_MAX;
const long long llinf = LLONG_MAX;
const int lg = 25; // lg + 1
template<class T> bool minimize(T &a, T b) {
return a > b ? (a = b, true) : false;
}
template<class T> bool maximize(T &a, T b) {
return a < b ? (a = b, true) : false;
}
template<class T> bool add(T &a, T b) {
a += b;
while (a > mod) a -= mod;
return true;
}
int n, m, k;
int g[505][505];
vector<pair<int, int> > adj[N];
int id[N];
bool special[N];
namespace sub1 {
void floyd(void) {
for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) {
minimize(g[i][j], g[i][k] + g[k][j]);
}
}
void solve(void) {
floyd();
int ans = g[0][0];
for (int a = 1; a <= k; ++a)
for (int b = 1; b <= k; ++b)
for (int c = 1; c <= k; ++c)
for (int d = 1; d <= k; ++d) {
if (a == b || a == c || a == d || b == c || b == d || c == d) continue;
int x = id[a], y = id[b], z = id[c], t = id[d];
if (g[x][y] + g[z][t] < ans && g[x][y] != g[0][0] && g[z][t] != g[0][0])
minimize(ans, g[x][y] + g[z][t]);
}
cout << ans;
}
}
namespace full {
int d[N], from[N];
typedef pair<int, int> node;
pair<int, pair<int, int> > dijkstra_special(void) { // from special to another
memset(d, 0x3f, sizeof d);
memset(from, 0, sizeof from);
priority_queue<node, vector<node>, greater<node> > q;
for (int i = 1; i <= n; ++i) {
if (special[i]) {
q.push({0, i});
from[i] = i;
d[i] = 0;
}
}
while (q.size()) {
int u = q.top().se; q.pop();
for (auto i : adj[u]) {
int v = i.fi, l = i.se;
if (d[u] + l < d[v]) {
d[v] = d[u] + l;
from[v] = from[u];
q.push({d[v], v});
}
}
}
int ans = d[0], s = 1, t = 1;
for (int u = 1; u <= n; ++u) {
for (auto [v, w] : adj[u]) if (from[u] != from[v]) {
if (minimize(ans, d[u] + d[v] + w)) s = u, t = v;
}
}
return {ans, {s, t}};
}
pair<int, int> dijstra(int s) { // shortest path from source
memset(d, 0x3f, sizeof d);
priority_queue<node, vector<node>, greater<node> > q;
q.push({0, s});
d[s] = 0;
while (q.size()) {
int u = q.top().se; q.pop();
if (special[u]) return {d[u], u};
for (auto i : adj[u]) {
int v = i.fi, l = i.se;
if (d[u] + l < d[v]) {
d[v] = d[u] + l;
q.push({d[v], v});
}
}
}
return {inf, 0};
}
void solve(void) {
int dis1, dis2, s1, t1, s2, t2;
// int ans = inf;
auto ans1 = dijkstra_special();
dis1 = ans1.fi, s1 = ans1.se.fi, t1 = ans1.se.se;
special[s1] = special[t1] = false;
auto ans2 = dijkstra_special();
dis2 = ans2.fi, s2 = ans2.se.fi, t2 = ans2.se.se;
cout << dis1 + dis2;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen(file".inp", "r",stdin);
// freopen(file".out", "w",stdout);
cin >> n >> m >> k;
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= m; ++i) {
int u, v, c;
cin >> u >> v >> c;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
g[u][v] = c;
g[v][u] = c;
}
for (int i = 1; i <= k; ++i) {
int x;
cin >> x;
id[i] = x;
special[x] = true;
}
// if (n <= 50) {
// sub1::solve();
// return 0;
// }
full::solve();
return 0;
}
Compilation message
RelayMarathon.cpp: In function 'void full::solve()':
RelayMarathon.cpp:114:27: warning: variable 's2' set but not used [-Wunused-but-set-variable]
114 | int dis1, dis2, s1, t1, s2, t2;
| ^~
RelayMarathon.cpp:114:31: warning: variable 't2' set but not used [-Wunused-but-set-variable]
114 | int dis1, dis2, s1, t1, s2, t2;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
41428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
41428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
52112 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
41428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
