Advertisement
konchin_shih

a129

Feb 5th, 2021
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #include"./template/headers.hpp"
  2.  
  3. //#define MULTI_TASKCASE
  4. using namespace abb;
  5. using namespace output;
  6. using namespace rit;
  7. using namespace wit;
  8.  
  9. inline void init() {
  10.  
  11. }
  12.  
  13. struct edge {
  14.     int b, w;
  15.     edge(int x, int y): b(x), w(y) {}
  16. };
  17. bool operator<(edge a, edge b) {return a.w > b.w;}
  18.  
  19. inline void solve() {
  20.     int n, m;
  21.     while (cin >> n >> m) {
  22.         V<V<edge>> v(n);
  23.         for (int i = 0; i != m; i++) {
  24.             static int a, b, w;
  25.             cin >> a >> b >> w;
  26.             v[a].emplace_back(b, w);
  27.             v[b].emplace_back(a, w);
  28.         }
  29.         V<bool> vis(n, false);
  30.         V<ll> d(n, 1e15);
  31.         PQ<edge> pq; pq.emplace(0, d[0] = 0);
  32.         for (int i = 0; i < n; i++) {
  33.             static int a; a = ~0u;
  34.             while (pq.size() && vis[a = pq.top().b]) pq.pop();
  35.             if (!~a) break;
  36.             vis[a] = true;
  37.             for (const auto& i : v[a])
  38.                 if (!vis[i.b] && i.w < d[i.b])
  39.                     pq.emplace(i.b, d[i.b] = i.w);
  40.         }
  41.         if (find(d.begin(), d.end(), 1e15) != d.end())
  42.             cout << -1 << endl;
  43.         else
  44.             cout << accumulate(d.begin(), d.end(), 0LL) << endl;
  45.     }
  46. }
  47.  
  48. main() {
  49.     ios::sync_with_stdio(false);
  50.     init();
  51.     int t = 1;
  52. #ifdef MULTI_TASKCASE
  53.     cin >> t; cin.ignore();
  54. #endif
  55.     while (t--) solve();
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement