#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 300001;
vector <ll> bit(nmax);
vector <vector <pll> > dp(nmax);
map <pii, bool> used;
map <int, int> cnt;
vector <vector <pll> > g(nmax);
priority_queue <pair<ll, pii> > q;
void upd(int u, int x, ll len){
bool tt;
tt = false;
for(int j = 0; j < 4; j++){
if(dp[u][j].s == x){
tt = true;
if(len > dp[u][j].f) continue;
dp[u][j].f = len;
q.push({-dp[u][j].f, {u, dp[u][j].s}});
}
}
if(!tt){
if(len < dp[u].back().f)
dp[u].pb({len, x}), q.push({-len, {u, x}});
}
sort(dp[u].begin(), dp[u].end());
if(dp[u].size() > 4)
dp[u].pop_back();
}
int main(){
int n, k, m; cin >> n >> m >> k;
for(int i = 1; i <= m; i++){
int u, v; cin >> u >> v;
ll w; cin >> w;
g[u].pb({v, w});
g[v].pb({u, w});
}
vector <int> sources;
for(int i = 1 ;i <= k; i++){
int x; cin >> x;
sources.pb(x);
}
// cout << 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j < 4; j++)
dp[i].pb({1e18, 0});
}
// cout << 1;
for(int to : sources){
dp[to][0] = {0, to};
q.push({0, {to, to}});
}
//cout << 1;
while(!q.empty()){
int v = q.top().s.f, y = q.top().s.s;
ll val = -q.top().f;
q.pop();
if(used[{v, y}] || cnt[v] >= 4) continue;
used[{v, y}] = true;
cnt[v]++
for(auto ed : g[v]){
int to = ed.f;
ll len = ed.s + val;
upd(to, y, len);
}
}
vector <pair<ll, pii> > vec;
for(int to : sources){
for(int j = 0; j < 4; j++){
if(dp[to][j].f != 1e18)
vec.pb({dp[to][j].f, {to, dp[to][j].s}});
}
}
sort(vec.begin(), vec.end());
int cnt[n + 1];
fill(cnt, cnt + n + 1, 0);
set <pii> st;
vector <pair<ll, pii> > cand;
for(auto to : vec){
if(cand.size() > 30) break;
if(to.s.f == to.s.s) continue;
if(st.find({to.s.f, to.s.s}) != st.end()) continue;
st.insert({to.s.f, to.s.s});
if(cnt[to.s.f] < 4 && cnt[to.s.s] < 4){
cand.pb(to);
cnt[to.s.f]++;
cnt[to.s.s]++;
}
}
// cout << 1;
ll ans = 1e18;
for(int i = 0; i < cand.size(); i++){
for(int j =0; j < cand.size(); j++){
set <int> st;
st.insert(cand[i].s.f);
st.insert(cand[i].s.s);
st.insert(cand[j].s.f);
st.insert(cand[j].s.s);
if(st.size() == 4){
ans = min(ans, cand[i].f + cand[j].f);
}
}
}
cout << ans;
return 0;
}
Compilation message
RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:71:17: error: expected ';' before 'for'
71 | cnt[v]++
| ^
| ;
72 | for(auto ed : g[v]){
| ~~~
RelayMarathon.cpp:67:12: warning: unused variable 'val' [-Wunused-variable]
67 | ll val = -q.top().f;
| ^~~
RelayMarathon.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> >, std::allocator<std::pair<long long int, std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int i = 0; i < cand.size(); i++){
| ~~^~~~~~~~~~~~~
RelayMarathon.cpp:104:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> >, std::allocator<std::pair<long long int, std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int j =0; j < cand.size(); j++){
| ~~^~~~~~~~~~~~~
