fork download
copy 
  1. #include<bits/stdc++.h> //NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. using pii = pair<int, int>;
  8. template <class T> using heapmin = priority_queue<T, vector<T>, greater<T>>;
  9. const int N = 2e5 + 5;
  10. const int inf = 1e17;
  11. int n, m, k;
  12. int DB[N];
  13. bool isDB[N];
  14. vector<pii> G[N];
  15. namespace sub1 {
  16. int dist[N], ans[N];
  17. void dijkstra(int root) {
  18.     for (int i = 1; i <= n; i++) dist[i] = inf;
  19.  
  20.     dist[root] = 0;
  21.     heapmin<pii> Q;
  22.      Q.push({0, root});
  23.      while(!Q.empty()) {
  24.         int u = Q.top().sc, old = Q.top().ft;
  25.         Q.pop();
  26.         if (old != dist[u]) continue;
  27.         if (isDB[u] && u != root) ans[u] = min(ans[u], old);
  28.         for (pii item: G[u]) {
  29.             int v = item.ft, w = item.sc + old;
  30.             if (w < dist[v]) {
  31.                 dist[v] = w;
  32.                 Q.push({w, v});
  33.             }
  34.         }
  35.      }
  36. }
  37. void solve() {
  38.     for (int i = 1; i <= n; i++) ans[i] = inf;
  39.     for (int i = 1; i <= k; i++) {
  40.         dijkstra(DB[i]);
  41.     }
  42.     for (int i = 1; i <= k; i++) {
  43.         int u = DB[i];
  44.         if (ans[u] == inf) cout << "-1\n";
  45.         else cout << ans[u] << "\n";
  46.     }
  47. }
  48. };
  49.  
  50. namespace subfull {
  51. int dist[N], root[N], ans[N];
  52. using pipii = pair<int, pii>;
  53. void solve() {
  54.     for (int i = 1; i <= n; i++) ans[i] = inf, dist[i] = inf;
  55.     heapmin<pipii> Q;
  56.     for (int i = 1; i <= k; i++) {
  57.         int u = DB[i];
  58.         root[u] = u;
  59.         dist[u] = 0;
  60.         Q.push({0, {u, u}});
  61.     }
  62.     while(!Q.empty()) {
  63.         int old = Q.top().ft, u = Q.top().sc.ft, rt = Q.top().sc.sc;
  64.         Q.pop();
  65.         if (old != dist[u]) {
  66.             if (rt != root[u]) {
  67.                 ans[rt] = min(ans[rt], dist[u] + old);
  68.                 ans[root[u]] = min(ans[root[u]], dist[u] + old);
  69.             }
  70.             continue;
  71.         }
  72.         for (pii item: G[u]) {
  73.             int v = item.ft, w = item.sc + old;
  74.             if (rt != root[v]) {
  75.                 ans[rt] = min(ans[rt], dist[v] + w);
  76.                 ans[root[v]] = min(ans[root[v]], dist[v] + w);
  77.             }
  78.  
  79.             if (w < dist[v]) {
  80.                 dist[v] = w;
  81.                 root[v] = rt;
  82.                 Q.push({w, {v, rt}});
  83.             }
  84.         }
  85.     }
  86.     for (int i = 1; i <= k; i++) {
  87.         int u = DB[i];
  88.         if (ans[u] == inf) cout << "-1\n";
  89.         else cout << ans[u] << "\n";
  90.     }
  91. }
  92. };
  93. signed main() {
  94.     cin.tie(NULL)->sync_with_stdio(false); cout.tie(NULL);
  95.     if (ifstream("DB.INP")) {
  96.         freopen("DB.INP", "r", stdin);
  97.         freopen("DB.OUT", "w", stdout);
  98.     }
  99.     cin >> n >> m >> k;
  100.     for (int i = 1; i <= m; i++) {
  101.         int u, v, w; cin >> u >> v >> w;
  102.         G[u].push_back({v, w});
  103.         G[v].push_back({u, w});
  104.     }
  105.     for (int i = 1; i <= k; i++){
  106.         cin >> DB[i];
  107.         isDB[DB[i]] = 1 ;
  108.     }
  109. //    if (n <= 200) return sub1::solve(), 0;
  110.     return subfull::solve(), 0;
  111.     return 0;
  112. }
  113.  
Success #stdin #stdout 0.01s 9732KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HkRsw9
language:
C++14 (gcc 8.3)
created:
14 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!