BOJ 18262 - Milk Pumping

BOJ 18262 - Milk Pumping

$N$ 제한이 작으므로 $1000$번 최단경로를 찾아줄 수 있고, $f$ 들을 오름차순 정렬해서 작은 $f$ 들을 가진 간선들부터 안써가며 각각의 최단경로를 찾아주어 $\dfrac f{d_{N}}$ 을 계산해줄 수 있다.

void solve() {  
   int n, m;  
   cin >> n >> m;  
   vector<vector<array<int, 3>>> edges(n);  
   vi flows;  
   for (int i = 0; i < m; i++) {  
      int u, v, c, f;  
      cin >> u >> v >> c >> f, u--, v--;  
      edges[u].pb({v, c, f});  
      edges[v].pb({u, c, f});  
      flows.pb(f);  
   }  
   ll ans = -2e15;  
   auto get_shortest = [&](int mn_flow_rate) {  
      vi dist(n, 1e9);  
      dist[0] = 0;  
      priority_queue<pi, vector<pi>, greater<>> pq;  
      pq.push({0, 0});  
      while (sz(pq)) {  
         auto[cur_d, cur] = pq.top();  
         pq.pop();  
         if (dist[cur] < cur_d) continue;  
         for (const auto&[to, c, f]: edges[cur]) {  
            if (f < mn_flow_rate) continue;  
            if (dist[to] > cur_d + c) pq.push({dist[to] = cur_d + c, to});  
         }  
      }  
      debug(mn_flow_rate, dist[n - 1]);  
      if (dist[n - 1] != 1e9) {  
         ans = max(ans, 1ll * mn_flow_rate * 1'000'000 / dist[n - 1]);  
      }  
   };  
   uniq(flows);  
   for (int f: flows) {  
      get_shortest(f);  
   }  
   cout << ans;  
}