#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;
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 < 5; 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() > 5)
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 < 5; 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}]) continue;
used[{v, y}] = true;
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 < 5; 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);
vector <pair<ll, pii> > cand;
for(auto to : vec){
if(cand.size() > 100) break;
if(cnt[to.s.f] < 5 && cnt[to.s.s] < 5){
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:97: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]
97 | for(int i = 0; i < cand.size(); i++){
| ~~^~~~~~~~~~~~~
RelayMarathon.cpp:98: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]
98 | for(int j =0; j < cand.size(); j++){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
16724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
16724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
564 ms |
51576 KB |
Output is correct |
| 2 |
Correct |
34 ms |
31820 KB |
Output is correct |
| 3 |
Execution timed out |
6054 ms |
219808 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
16724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
