#include <bits/stdc++.h>
using namespace std;
const long long MAX = 0x3f3f3f3f3f3f3f3f;
template<typename T>
bool minimize(T&x,T y) {
return x > y ? x = y, true : false;
}
int buckSiz;
pair<long long, int> bucket[8];
struct FourMin {
pair<long long, int> v[4];
FourMin() {
for (int i = 0; i < 4; ++i) {
v[i] = make_pair(MAX, -1);
}
}
FourMin operator + (long long x) const {
FourMin tmp;
for (int i = 0; i < 4; ++i) {
if (v[i].second != -1) {
tmp.v[i].first = v[i].first + x;
tmp.v[i].second = v[i].second;
}
}
return tmp;
}
bool update(const FourMin& val) {
buckSiz = 0;
for (int i = 0; i < 4; ++i) {
bucket[buckSiz++] = v[i];
bucket[buckSiz++] = val.v[i];
}
sort(bucket, bucket+buckSiz);
bool flag = false;
int j = 0;
for (int i = 0; i < buckSiz; ++i) {
bool found = false;
for (int k = 0; k < j; ++k) {
if (v[k].second == bucket[i].second && bucket[i].second != -1) {
found = true;
break;
}
}
if (!found) {
flag |= v[j] > bucket[i];
v[j++] = bucket[i];
if (j == 4) {
break;
}
}
}
return flag;
}
void update(const pair<long long, int>& x) {
buckSiz = 0;
for (int i = 0; i < 4; ++i) {
bucket[buckSiz++] = v[i];
}
bucket[buckSiz++] = x;
sort(bucket,bucket+buckSiz);
int j = 0;
for (int i = 0; i < buckSiz; ++i) {
bool found = false;
for (int k = 0; k < j; ++k) {
if (v[k].second == bucket[i].second && bucket[i].second != -1) {
found = true;
break;
}
}
if (!found) {
v[j++] = bucket[i];
if (j == 4) {
break;
}
}
}
}
bool operator < (const FourMin& val) const {
for (int i = 0; i < 4; ++i) {
if (v[i].first != val.v[i].first) {
return v[i].first > val.v[i].first;
}
}
return true;
}
bool operator != (const FourMin& val) const {
for (int i = 0; i < 4; ++i) {
if (v[i] != val.v[i]) {
return true;
}
}
return false;
}
friend ostream& operator << (ostream& os, const FourMin& val) {
for (int i = 0; i < 4; ++i) {
os << i << " -> " << val.v[i].first << ' ' << val.v[i].second << '\n';
os << "------\n";
}
return os;
}
};
const int N = 1e5+7;
int numNode, numEdge, numSpec;
vector<pair<int,int>> adj[N];
vector<int> specs;
FourMin dist[N];
long long res;
int src[2], snk[2];
int candSiz;
pair<long long, pair<int,int>> candidates[N*4];
void dijkstra() {
priority_queue<pair<FourMin, int>> heap;
for (int x : specs) {
dist[x].v[0] = make_pair(0, x);
heap.emplace(dist[x], x);
}
while (!heap.empty()) {
int u = heap.top().second;
FourMin w = heap.top().first;
// cerr << " >> " << u << '\n';
heap.pop();
if (dist[u] != w) {
continue;
}
for (pair<int,int> e : adj[u]) {
int v = e.first;
int w = e.second;
// cerr << u << ": \n" << (dist[u]);
// cerr << v << ": \n" << dist[v];
if (dist[v].update(dist[u] + w)) {
// cerr << v << ": \n" << dist[v];
heap.emplace(dist[v], v);
}
}
}
}
bool deepdiff(const pair<int,int>& a, const pair<int,int>& b) {
return a.first != b.first && a.first != b.second && a.second != b.first && a.second != b.second;
}
void processCaseOne() {
pair<int,int> clos = candidates[0].second;
// cerr << " >> ";
// cerr << clos.first << ' ' << clos.second << '\n';
for (int i = 1; i < candSiz; ++i) {
if (deepdiff(clos, candidates[i].second)) {
res = candidates[0].first + candidates[i].first;
src[0] = clos.first;
snk[0] = clos.second;
src[1] = candidates[i].second.first;
snk[1] = candidates[i].second.second;
return;
}
}
}
void updateResult(long long r, int _src1, int _snk1, int _src2, int _snk2) {
if (minimize(res, r)) {
src[0] = _src1;
snk[0] = _snk1;
src[1] = _src2;
snk[1] = _snk2;
}
}
void processCaseTwo() {
int beg[2];
beg[0] = candidates[0].second.first;
beg[1] = candidates[0].second.second;
FourMin fm[2];
for (int i = 0; i < candSiz; ++i) {
for (int j = 0; j < 2; ++j) {
if (candidates[i].second.first == beg[j] && candidates[i].second.second != beg[!j]) {
fm[j].update(make_pair(candidates[i].first, candidates[i].second.second));
} else if (candidates[i].second.second == beg[j] && candidates[i].second.first != beg[!j]) {
fm[j].update(make_pair(candidates[i].first, candidates[i].second.first));
}
}
}
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
if (fm[0].v[i].second != fm[1].v[j].second) {
updateResult(fm[0].v[i].first+fm[1].v[j].first, beg[0], fm[0].v[i].second, beg[1], fm[1].v[j].second);
}
}
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
freopen("marathon.inp", "r", stdin);
freopen("marathon.out", "w", stdout);
cin >> numNode >> numEdge >> numSpec;
for (int i = 0; i < numEdge; ++i) {
int x, y, w;
cin >> x >> y >> w;
adj[x].emplace_back(y, w);
adj[y].emplace_back(x, w);
}
for (int i = 0; i < numSpec; ++i) {
int x;
cin >> x;
specs.push_back(x);
}
dijkstra();
// for (int i = 1; i <= numNode; ++i) {
// for (int j = 0; j < 4; ++j) {
// cerr << i << " : " << j << " -> " << dist[i].v[j].first << ' ' << dist[i].v[j].second << '\n';
// }
// }
for (int i = 1; i <= numNode; ++i) {
for (int j = 0; j < 4; ++j)
for (int k = j+1; k < 4; ++k) {
if (dist[i].v[j].second != -1 && dist[i].v[k].second != -1) {
candidates[candSiz++] = make_pair(dist[i].v[j].first+dist[i].v[k].first, make_pair(dist[i].v[j].second, dist[i].v[k].second));
}
}
}
sort(candidates, candidates+candSiz);
processCaseOne();
processCaseTwo();
cout << res;
// for (int i = 0; i < 2; ++i) {
// cerr << " >>> " << src[i] << ' ' << snk[i] << '\n';
// }
return 0;
}
Compilation message
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:206:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
206 | freopen("marathon.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:207:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
207 | freopen("marathon.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
