← 전체 글로 돌아가기
competitive-programming2021년 1월 21일1분 분량

[백준] 10675. Cow Routing 풀이

수정일: 2021년 1월 21일

Ad hoc
지원 언어:enko

#Problem

10675. Cow Routing

#Approach

출발지와 도착지를 포함하는 route를 가진 비행편 중 비용이 최소인 것을 찾으면 되는 문제다.

ans←∞ans \leftarrow \infty
N개의 비행편에 대해서, 각 도시를 순회하면서 아래를 수행.

  1. 여기가 시작점이면, flag←trueflag \leftarrow true
  2. 여기가 도착점이고, flag==trueflag == true 이면 최솟값 업데이트

모든 비행편 순회 후 ansans 값이 ∞\infty 이라면 −1-1, 아니라면 ansans 값을 출력.

#Code

/**
 * author: jooncco
 * written: 2021. 1. 21. Thu. 22:39:49 [UTC+9]
 **/

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

const int INF= 9999;
int A,B,N;

int main() {

    cin >> A >> B >> N;
    int ans= INF;
    int price, cities;
    for (int plane=0; plane < N; ++plane) {
        cin >> price >> cities;
        bool start= 0, end= 0;
        int here;
        for (int j= 0; j < cities; ++j) {
            cin >> here;
            if (here == A) start= 1;
            if (here == B && start) {
                end= 1;
            }
        }
        if (end) ans= min(ans,price);
    }
    cout << (ans == INF ? -1 : ans);
}

#Complexity

  • Time: O(N⋅lengthOfRoute)O(N \cdot lengthOfRoute)
  • Space: O(1)O(1)