Advertisement
mzh_pb

Untitled

Dec 10th, 2023
694
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. #define int int64_t
  5.  
  6. #define rng(i, a, b) for (int i = a; i < b; i++)
  7. #define rep(i, b) rng(i, 0, b)
  8. #define gnr(i, a, b) for (int i = b - 1; i >= a; i--)
  9. #define per(i, b) gnr(i, 0, b)
  10.  
  11. #define all(x) begin(x), end(x)
  12. #define sz(x) int(size(x))
  13.  
  14. #define pb push_back
  15. #define eb emplace_back
  16. #define lb lower_bound
  17. #define ub upper_bound
  18.  
  19. #define f first
  20. #define s second
  21.  
  22. using namespace std;
  23. using namespace __gnu_pbds;
  24.  
  25. const int INF = 1e18;
  26.  
  27. void solve() {
  28.     int n, m, t;
  29.     cin >> n >> m >> t;
  30.  
  31.     vector<int> c(n);
  32.     rep(i, n) {
  33.         cin >> c[i];
  34.     }
  35.  
  36.     vector<vector<pair<int, int>>> g(n);
  37.     rep(i, m) {
  38.         int u, v, w;
  39.         cin >> u >> v >> w;
  40.         u--; v--;
  41.         g[u].pb({v, w});
  42.         g[v].pb({u, w});
  43.     }
  44.  
  45.     vector<int> dist(n, INF);
  46.     dist[0] = 0;
  47.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  48.     pq.push({0, 0});
  49.     while (!pq.empty()) {
  50.         int u = pq.top().s;
  51.         pq.pop();
  52.         for (auto [v, w] : g[u]) {
  53.             if (dist[u] + w < dist[v]) {
  54.                 dist[v] = dist[u] + w;
  55.                 pq.push({dist[v], v});
  56.             }
  57.         }
  58.     }
  59.  
  60.     vector<vector<int>> dg(n);
  61.     rng(u, 1, n) {
  62.         int to = INF;
  63.         for (auto [v, w] : g[u]) {
  64.             if (w + dist[v] == dist[u]) {
  65.                 to = min(to, v);
  66.             }
  67.         }
  68.         dg[to].pb(u);
  69.     }
  70.  
  71.     vector<int> dep(n);
  72.     queue<int> q;
  73.     q.push(0);
  74.     while (!q.empty()) {
  75.         int u = q.front();
  76.         q.pop();
  77.         for (int v : dg[u]) {
  78.             dep[v] = dep[u] + 1;
  79.             q.push(v);
  80.         }
  81.     }
  82.  
  83.     vector<int> ord(n);
  84.     iota(all(ord), 0);
  85.     sort(all(ord), [&](int a, int b) {
  86.         return dep[a] > dep[b];
  87.     });
  88.  
  89.     for (int u : ord) {
  90.         for (int v : dg[u]) {
  91.             c[u] += c[v];
  92.         }
  93.     }
  94.  
  95.     int ans = 0;
  96.     rng(i, 1, n) {
  97.         ans = max(ans, (dist[i] - t) * c[i]);
  98.     }
  99.     cout << ans << '\n';
  100. }
  101.  
  102. int32_t main() {
  103. #ifndef LOCAL
  104.     freopen("shortcut.in", "r", stdin);
  105.     freopen("shortcut.out", "w", stdout);
  106. #endif
  107.     ios::sync_with_stdio(false);
  108.     cin.tie(nullptr);
  109.  
  110.     int tc = 1;
  111.     // cin >> tc;
  112.     while (tc--) {
  113.         solve();
  114.     }
  115.  
  116.     return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement