Paste Search Dynamic
Recent pastes
max
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. #define pii pair<int, int>
  6. #define ff first
  7. #define ss second
  8. #define INF (int)1e9
  9. using namespace std;
  10.  
  11. int n, m, r;
  12. int T[121];
  13. vector<pii> edge[121];
  14.  
  15. priority_queue<pii, vector<pii>, greater<pii>> pq;
  16. int dist[121];
  17.  
  18. int bfs(int s){
  19.         for(int i = 1; i <= n; i++) dist[i] = INF;
  20.        
  21.         int res = 0;
  22.         pq.emplace(0, s);
  23.         dist[s] = 0;
  24.         while(!pq.empty()){
  25.                 pii v = pq.top(); pq.pop();
  26.                 if(dist[v.ss] != v.ff) continue;
  27.                
  28.                 res += T[v.ss];
  29.                
  30.                 for(pii u : edge[v.ss]){
  31.                         if(v.ff+u.ss > m) continue;
  32.                        
  33.                         if(dist[u.ff] > v.ff+u.ss){
  34.                                 dist[u.ff] = v.ff+u.ss;
  35.                                 pq.emplace(v.ff+u.ss, u.ff);
  36.                         }
  37.                 }
  38.         }
  39.        
  40.         return res;
  41. }
  42.  
  43. int main(){
  44.         scanf("%d %d %d", &n, &m, &r);
  45.         for(int i = 1; i <= n; i++) scanf("%d", &T[i]);
  46.         while(r--){
  47.                 int a, b, l; scanf("%d %d %d", &a, &b, &l);
  48.                
  49.                 edge[a].emplace_back(b, l);
  50.                 edge[b].emplace_back(a, l);
  51.         }
  52.        
  53.         int ans = 0;
  54.         for(int i = 1; i <= n; i++) ans = max(ans, bfs(i));
  55.        
  56.         printf("%d", ans);
  57.        
  58.         return 0;
  59. }
Parsed in 0.005 seconds