fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long 
  4. #define el cout << '\n'
  5. #define ii pair<ll, ll>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 2e5;
  12. const ll INF = 1e18;
  13.  
  14. struct Node
  15. {
  16.     int top, source;
  17.     ll dist;
  18.  
  19.     Node(int top = 0, int source = 0, ll dist = 0) :
  20.         top(top), source(source), dist(dist) {};
  21.     bool operator < (const Node &other) const
  22.     {
  23.         return dist > other.dist || (dist == other.dist && source > other.source);
  24.     }
  25. };
  26.  
  27. int n, m, k;
  28. vector<ii> adj[maxn + 10];
  29. ii ans[maxn + 10], d[maxn + 10];
  30. int p[maxn + 10];
  31. priority_queue<Node> pq;
  32.  
  33. int main()
  34. {
  35.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  36.     if (fopen("FPAIR.INP", "r"))
  37.     {
  38.         freopen("FPAIR.INP", "r", stdin);
  39.         freopen("FPAIR.OUT", "w", stdout);
  40.     }
  41.  
  42.     cin >> n >> m >> k;
  43.     for (int i = 1; i <= n + k; i++)
  44.     {
  45.         d[i] = {INF, INF};
  46.         ans[i] = {INF, INF};
  47.     }
  48.     for (int i = 1; i <= k; i++)
  49.     {
  50.         cin >> p[i];
  51.         adj[p[i]].push_back({n + i, 0});
  52.         adj[n + i].push_back({p[i], 0});
  53.         pq.push(Node(n + i, n + i, 0));
  54.         d[n + i] = {0, n + i};
  55.     }
  56.  
  57.     // Initialize sources and handle same location
  58.  
  59.     for (int i = 1; i <= m; i++)
  60.     {
  61.         int x, y;
  62.         ll w;
  63.         cin >> x >> y >> w;
  64.         adj[x].push_back({y, w});
  65.         adj[y].push_back({x, w});
  66.     }
  67.  
  68.     while (pq.size())
  69.     {
  70.         Node t = pq.top();
  71.         pq.pop();
  72.         int top = t.top;
  73.         ll dist = t.dist;
  74.         int source = t.source;
  75.  
  76.         if (ii(dist, source) != d[top])
  77.             continue;
  78.  
  79.         for (ii pr : adj[top])
  80.         {
  81.             int next_top = pr.fi;
  82.             ll w = pr.se;
  83.             ll new_dist = dist + w;
  84.  
  85.             if (d[next_top].se != INF && d[next_top].se != source)
  86.             {
  87.                 ll total_dist = new_dist + d[next_top].fi;
  88.                 int other_source = d[next_top].se;
  89.                 ans[source] = min(ans[source], {total_dist, other_source});
  90.                 ans[other_source] = min(ans[other_source], {total_dist, source});
  91.             }
  92.  
  93.             if (d[next_top] > ii(new_dist, source))
  94.             {
  95.                 d[next_top] = ii(new_dist, source);
  96.                 pq.push(Node(next_top, source, new_dist));
  97.             }
  98.         }
  99.     }
  100.  
  101.     for (int i = 1; i <= k; i++)
  102.         cout << ans[i + n].se - n << ' ';
  103. }
Success #stdin #stdout 0.01s 9204KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IeOSy3
language:
C++14 (gcc 8.3)
created:
2 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!