[백준 10675] Cow Routing (C#, C++) - soo:bak

문제 링크

10675번 - Cow Routing

설명

여러 노선이 주어질 때, 하나의 노선만 이용해 A에서 B로 갈 수 있는 최소 비용을 구하는 문제입니다.

접근법

각 노선에 대해 도시 목록을 순서대로 확인합니다.
A가 먼저 나오고 이후에 B가 나오면 해당 노선의 비용을 후보로 갱신합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.In.ReadToEnd().Split();
    var idx = 0;
    var a = int.Parse(parts[idx++]);
    var b = int.Parse(parts[idx++]);
    var n = int.Parse(parts[idx++]);

    var best = int.MaxValue;
    for (var i = 0; i < n; i++) {
      var cost = int.Parse(parts[idx++]);
      var cnt = int.Parse(parts[idx++]);
      var seenA = false;
      var ok = false;

      for (var j = 0; j < cnt; j++) {
        var city = int.Parse(parts[idx++]);
        if (city == a) seenA = true;
        if (seenA && city == b) ok = true;
      }

      if (ok && cost < best) best = cost;
    }

    Console.WriteLine(best == int.MaxValue ? -1 : best);
  }
}

C++

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

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

  int a, b, n; cin >> a >> b >> n;
  int best = 1e9;

  for (int i = 0; i < n; i++) {
    int cost, cnt; cin >> cost >> cnt;
    bool seenA = false, ok = false;
    for (int j = 0; j < cnt; j++) {
      int city; cin >> city;
      if (city == a) seenA = true;
      if (seenA && city == b) ok = true;
    }
    if (ok && cost < best) best = cost;
  }

  cout << (best == 1e9 ? -1 : best) << "\n";

  return 0;
}