Problem


Key Idea

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

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

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

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


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


Implementation

/**
 * 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);
}

Tags:

Updated:

Leave a comment