[백준] 10675. Cow Routing 풀이

Problem

10675. Cow Routing

Approach

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

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

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

모든 비행편 순회 후 \(ans\) 값이 \(\infty\) 이라면 \(-1\), 아니라면 \(ans\) 값을 출력.

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 \cdot lengthOfRoute)\)
• Space: \(O(1)\)