BOJ 24024 - 삼색 그래프

BOJ 24024 - 삼색 그래프

우선 $X$ 를 모두 쓰는것이 최적이므로 모두 쓴다고 하면 빨간색에 $k$ 를 쓰면 파란색엔 $X-k$ 를 쓰게된다.

이것이 왜 최단거리에 대해서 uni-modal한 개형이 생기는지 사실 잘 모르겠는데 proof by ac로 삼분탐색을 이용해 다익스트라를 여러번 돌려 맞을 수 있었다.

struct Edge {
   int to, w, p;
};

void solve() {
   int n, m, x;
   cin >> n >> m >> x;
   vector<vector<Edge>> edges(n);
   for (int i = 0; i < m; i++) {
      int u, v, w, p;
      cin >> u >> v >> w >> p, u--, v--;
      edges[u].pb({v, w, p});
      edges[v].pb({u, w, p});
   }

   auto get = [&](int red, int blue) {
      vi dist(n, 2e18);

      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 (auto &e: edges[cur]) {
            int w = e.w;
            if (e.p == 1) w += red;
            if (e.p == 2) w += blue;
            if (dist[e.to] > cur_d + w) pq.push({dist[e.to] = cur_d + w, e.to});
         }
      }

      return dist[n - 1];
   };
   int l = 0, r = x;
   while (l < r - 2) {
      int p = (l * 2 + r) / 3;
      int q = (l + r * 2) / 3;

      int pv = get(p, x - p);
      int qv = get(q, x - q);

      if (pv > qv) r = q;
      else l = p;
   }
   int ans = 0;
   for (int i = l; i <= r; i++) {
      debug(i, get(i, x - i));
      maxa(ans, get(i, x - i));
   }
   cout << ans;
}