[백준 14938] 서강그라운드 (C#, C++) - soo:bak

문제 링크

14938번 - 서강그라운드

설명

N개의 지역에 각각 아이템이 있고, 지역 사이에는 양방향 도로가 있습니다. 낙하 지점을 정했을 때 수색 범위 m 이내로 도달 가능한 모든 지역의 아이템 합을 최대화하는 문제입니다.

접근법

각 지역에서 다른 모든 지역까지의 최단 거리를 구하면, 수색 범위 이내인 지역들의 아이템을 합산할 수 있습니다. N이 최대 100으로 작으므로 모든 지역을 출발점으로 다익스트라를 수행해도 시간 내에 충분합니다.

각 출발점에서 다익스트라를 수행한 뒤, 거리가 m 이하인 지역들의 아이템 수를 모두 더합니다. 이 값을 모든 출발점에 대해 계산하고, 그 중 최댓값을 출력합니다.

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    const int INF = int.MaxValue / 4;

    static int N, M, R;
    static int[] items = Array.Empty<int>();
    static List<(int to, int w)>[] adj = Array.Empty<List<(int, int)>>();

    static int CollectFrom(int start) {
      var dist = new int[N + 1];
      Array.Fill(dist, INF);
      dist[start] = 0;

      var pq = new PriorityQueue<int, int>();
      pq.Enqueue(start, 0);
      while (pq.Count > 0) {
        pq.TryDequeue(out var cur, out var d);
        if (d > dist[cur])
          continue;
        foreach (var e in adj[cur]) {
          var nd = d + e.w;
          if (nd < dist[e.to]) {
            dist[e.to] = nd;
            pq.Enqueue(e.to, nd);
          }
        }
      }

      var sum = 0;
      for (var i = 1; i <= N; i++) {
        if (dist[i] <= M)
          sum += items[i];
      }
      return sum;
    }

    static void Main(string[] args) {
      var first = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      N = first[0];
      M = first[1];
      R = first[2];

      items = new int[N + 1];
      var itemLine = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      for (var i = 1; i <= N; i++)
        items[i] = itemLine[i - 1];

      adj = new List<(int, int)>[N + 1];
      for (var i = 1; i <= N; i++)
        adj[i] = new List<(int, int)>();

      for (var i = 0; i < R; i++) {
        var line = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        var a = line[0];
        var b = line[1];
        var l = line[2];
        adj[a].Add((b, l));
        adj[b].Add((a, l));
      }

      var best = 0;
      for (var s = 1; s <= N; s++)
        best = Math.Max(best, CollectFrom(s));

      Console.WriteLine(best);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vp;

const int INF = 1e9;

int N, M, R;
vi item;
vector<vp> adj;

int dijkstra(int start) {
  vi dist(N + 1, INF);
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  dist[start] = 0;
  pq.push({0, start});

  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u])
      continue;
    for (auto [v, w] : adj[u]) {
      int nd = d + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        pq.push({nd, v});
      }
    }
  }

  int sum = 0;
  for (int i = 1; i <= N; i++) {
    if (dist[i] <= M)
      sum += item[i];
  }
  return sum;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> N >> M >> R;

  item.resize(N + 1);
  for (int i = 1; i <= N; i++)
    cin >> item[i];

  adj.resize(N + 1);
  for (int i = 0; i < R; i++) {
    int a, b, l; cin >> a >> b >> l;
    adj[a].push_back({b, l});
    adj[b].push_back({a, l});
  }

  int best = 0;
  for (int s = 1; s <= N; s++)
    best = max(best, dijkstra(s));

  cout << best << "\n";

  return 0;
}