[C++] 27848번 Moo Route II - 자료 구조, 그리디, 정렬, 너비 우선 탐색

27848번 Moo Route II

1. 문제

• 나라에는 1부터 N까지 번호가 매겨진 N개의 공항이 있고 M개의 시간 여행이 가능한 비행기가 있다. \((1 \leq N, M \leq 200,000)\). 비행기 \(j\)는 공항 \(c_j\) 시각 \(r_j\)에서 공항 \(d_j\) 시각 \(s_j\)에 착륙한다. \((0 \leq r_j, s_j \leq 10^9, s_j < r_j is possible)\). 게다가 공항에서 환승할 때는 \(a_i\)만큼의 시간이 걸린다. \((1 \leq a_i \leq 10^9)\). Bessie는 도시 1, 시각 0에서 시작할 때 1부터 N까지의 공항으로 각각 도착했을 때 최단 시각은 얼마인가?

<입력>

• -1- N, M
• -M- \(c_j, r_j, d_j, s_j (1 \leq c_j, d_j \leq N, 0 \leq r_j, s_j \leq 10^9)\)
• -1- \(a_i)

<출력>

• N개의 줄에 최단 시각을 출력하시오. 만약 갈 수 없다면 -1을 출력하시오.

 

2. 재정의

• Pass

 

3. 실수한 점, 개선할 점

• priority_queue는 <가 참이어야 >가 되도록 바뀐다.

 

4. 해결 방법

• 공항이 서로 연결되어 있는 그래프를 생각하자. 최단 시각으로 도착할 때 똑같은 비행기를 두 번 이상 탈 일은 없기 때문에 1번 공항에서부터 BFS를 실시하며 되는 비행기는 타고 안 되는 비행기는 안타며 탄 비행기는 그냥 제거해 버리면 된다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct Edge {
    // 도착지점
    int v;
    // 출발, 도착 시각
    int r, s;
} typedef Edge;

struct cmp {
    bool operator()(Edge a, Edge b) {
        return a.r < b.r;
    }
};

const int INF = 1000000001;
const int MAX_N = 200001;
const int MAX_M = 200001;



queue<int> q;
vector<priority_queue<Edge, vector<Edge>, cmp>> graph(MAX_N);

int N, M;
int A[MAX_N];

vector<int> arr_time(MAX_N);

bool compare(Edge a, Edge b) {
    return a.r > b.r;
}

void input() {
    fill(arr_time.begin(), arr_time.end(), INF);
    arr_time[1] = 0;
    
    cin >> N >> M;
    for(int i=0; i<M; i++) {
        int c, r, d, s;
        cin >> c >> r >> d >> s;
        Edge edge = {d, r, s};
        graph[c].push(edge);
    }
    for(int i=1; i<=N; i++)
        cin >> A[i];
    A[1] = 0;
}

void solve() {
    q.push(1);
    
    while(!q.empty()) {
        int node = q.front(); q.pop();
        
        while(!graph[node].empty()) {
            Edge edge = graph[node].top();
            if(arr_time[node] + A[node] <= edge.r) {
                if(edge.s < arr_time[edge.v]) {
                    arr_time[edge.v] = edge.s;
                    q.push(edge.v);
                }
                graph[node].pop();
            }
            else
                break;
        }
    }
    for(int i=1; i<=N; i++)
        cout << (arr_time[i] == INF ? -1:arr_time[i]) << '\n';
}

int main() {
    ios_base::sync_with_stdio();
    cin.tie(0); cout.tie(0);
    
    input();
    
    solve();
    
    return 0;
}

 

<문제 바로가기>

https://www.acmicpc.net/problem/27848

27848번: Moo Route II