This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
struct datax{
ll u, v, w;
};
ll n, m, k, cities[100005], ans, t, u, v, w, dist[100005], h[100005], a, b, spe[100005];
ll flat[100005];
vector<ii> adj[100005];
datax queries[400005];
ii dijkstra(ll s){
priority_queue<ii, vector<ii>, greater<ii>> pq;
for(int i=1; i<=n; i++) dist[i] = 1e9;
dist[s]=0;
pq.push({0, s});
while(!pq.empty()){
ll val = pq.top().fi;
ll u = pq.top().se;
pq.pop();
if(dist[u]!=val) continue;
if(spe[u]){
return {dist[u], u};
}
for(auto edge:adj[u]){
ll v = edge.fi;
ll w = edge.se;
if(dist[v]>dist[u]+w){
dist[v] = dist[u]+w;
pq.push({dist[v], v});
}
}
}
return {1e9, 0};
}
void dijkstra2(){
priority_queue<ii, vector<ii>, greater<ii>> pq;
for(int i=1; i<=n; i++) dist[i] = 1e9;
for(int i=1; i<=n; i++){
if(!spe[i]) continue;
dist[i]=0;
pq.push({0, i});
h[i] = i;
}
while(!pq.empty()){
ll val = pq.top().fi;
ll u = pq.top().se;
pq.pop();
if(dist[u]!=val) continue;
for(auto edge:adj[u]){
ll v = edge.fi;
ll w = edge.se;
if(dist[v]==dist[u]+w) flat[v] = 1;
if(dist[v]>dist[u]+w){
dist[v] = dist[u]+w;
h[v] = h[u];
flat[v]=0;
pq.push({dist[v], v});
}
}
}
}
void inp(){
cin >> n >> m >> k;
for(int i=1; i<=m; i++){
cin >> u >> v >> w;
queries[i] = {u, v, w};
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for(int i=1; i<=k; i++){
cin >> cities[i];
spe[cities[i]]=1;
}
}
pair<ll, ii> choose(){
ll ans=LLONG_MAX, a=0, b=0;
for(int i=1; i<=m; i++){
ll u = queries[i].u, v = queries[i].v, w = queries[i].w;
if(flat[u]||flat[v]||h[u]!=h[v]){
ll t = dist[u] + dist[v] + w;
if(t<ans){
ans = t;
a = h[u];
b = h[v];
}
//cout << dist[u] << ' ' << dist[v] << '\n';
//cout << flat[u] << ' ' <<flat[v] << '\n';
}
}
return {ans, {a, b}};
}
ll nearest(ll a, ll b){
ii tmp1 = dijkstra(a);
ll c = tmp1.se;
ll t3 = tmp1.fi;
spe[c]=0;
ii tmp2 = dijkstra(b);
ll d = tmp2.se;
ll t4 = tmp2.fi;
spe[c]=1;
return t3+t4;
}
void solve(){
dijkstra2();
pair<ll, ii> tmp = choose();
ll t1 = tmp.fi;
ll a = tmp.se.fi;
ll b = tmp.se.se;
spe[a]=0, spe[b]=0;
dijkstra2();
ll t2 = choose().fi;
ll ans = t1+t2;
ans = min({ans, nearest(a, b), nearest(b, a)});
cout << ans;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
//freopen("cities.inp", "r", stdin);
//freopen("cities.out", "w", stdout);
inp();
solve();
return 0;
}
Compilation message (stderr)
RelayMarathon.cpp: In function 'long long int nearest(long long int, long long int)':
RelayMarathon.cpp:114:5: warning: unused variable 'd' [-Wunused-variable]
114 | ll d = tmp2.se;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |