fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ld long double
  5. #define FOR(i,l,r) for(ll i = (l), _r = (r); i <= _r; i++)
  6. #define FORNG(i,r,l) for(ll i = (r), _l = (l); i >= _l; i--)
  7. #define REP(i,r) for(ll i = 0, _r = (r); i < _r; i++)
  8. #define endl '\n'
  9. #define fi first
  10. #define se second
  11. #define pb push_back
  12. #define size(v) ((ll)(v).size())
  13. #define all(v) (v).begin(),(v).end()
  14. #define MASK(x) (1LL << (x))
  15. #define BIT(x,i) (((x) >> (i)) & 1)
  16.  
  17. const ll MOD = 1e9 + 7, N = 3e5 + 10, INF = 1e18, LOG = 21;
  18. ll n,m,k,dist[N],best[N];
  19. bool isP[N];
  20. pair<ll,ll> ans[N];
  21. vector<pair<ll,ll>> adj[N];
  22. int main(){
  23.     ios_base::sync_with_stdio(0);cin.tie(0);
  24.     cin>>n>>m>>k;
  25.     fill(dist + 1, dist + 1 + n + k, INF);
  26.     fill(best + 1, best + 1 + n + k, INF);
  27.     priority_queue<array<ll,3>, vector<array<ll,3>>, greater<array<ll,3>>> qu;
  28.     FOR(i,n + 1,n + k){
  29.         ll p;cin>>p;
  30.         adj[p].pb({i, 0});
  31.         adj[i].pb({p, 0});
  32.         best[i] = i;
  33.         dist[i] = 0;
  34.         qu.push({0, i, i});
  35.         isP[i] = 1;
  36.     }
  37.     FOR(i,1,m){
  38.         ll u,v,w;cin>>u>>v>>w;
  39.         adj[u].pb({v, w});
  40.         adj[v].pb({u, w});
  41.     }
  42.     while(!qu.empty()){
  43.         auto [d, b, u] = qu.top();
  44.         qu.pop();
  45.         if(d > dist[u] || b != best[u])continue;
  46.         for(auto [v, w] : adj[u]){
  47.             if(dist[u] + w == dist[v] && best[u] < best[v]){
  48.                 dist[v] = dist[u] + w;
  49.                 best[v] = best[u];
  50.                 qu.push({dist[v], best[v], v});
  51.             }
  52.             if(dist[u] + w < dist[v]){
  53.                 dist[v] = dist[u] + w;
  54.                 best[v] = best[u];
  55.                 qu.push({dist[v], best[v], v});
  56.             }
  57.         }
  58.     }
  59. //    FOR(i,1,n + k)cout<<i<<' '<<best[i]<<' '<<dist[i]<<endl;
  60.     FOR(i,1,n + k)ans[i] = {INF, INF};
  61.     FOR(u,1,n + k){
  62.         if(u != best[u] && isP[u]){
  63.             ans[best[u]] = min(ans[best[u]], {dist[u], u});
  64.             ans[u] = min(ans[u], {dist[u], best[u]});
  65.         }
  66.         for(auto [v, w] : adj[u]){
  67.             if(best[u] != best[v]){
  68.                 ans[best[u]] = min(ans[best[u]], {w + dist[u] + dist[v], best[v]});
  69.             }
  70.         }
  71.     }
  72.     FOR(i,n + 1,n + k)cout<<ans[i].se - n<<' ';
  73. }
Success #stdin #stdout 0.01s 11740KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/QaUMU9
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!