#include #include #include #include #include #define rep(i,a,b) for(int i=(a);i<(b);++i) #define INF 2147483647 using namespace std; // 우선순위 큐에 저장될 아이템: {시간, 현재 공항, 누적 비용} struct Item { int time, node, cost; // 시간을 기준으로 오름차순 정렬 bool operator>(const Item& other) const { return time > other.time; } }; struct Ticket { int to, cost, time; }; int T, N, M, K; vector> adjv; // dist[i] : i번 공항까지 가는 <비용, 시간>의 non-dominated 경로 맵 vector> dist; int main() { cin.tie(0)->sync_with_stdio(0); cin >> T; // while(T--) { // 문제에서는 T=1로 고정 cin >> N >> M >> K; adjv.assign(N + 1, vector()); dist.assign(N + 1, map()); rep(i, 0, K) { int u, v, c, d; cin >> u >> v >> c >> d; adjv[u].push_back({v, c, d}); } priority_queue, greater> pq; // 시작점: 1번 공항, 비용 0, 시간 0 dist[1][0] = 0; pq.push({0, 1, 0}); while (!pq.empty()) { Item current = pq.top(); pq.pop(); int c_time = current.time; int c_node = current.node; int c_cost = current.cost; // 큐에서 꺼낸 경로가 이미 더 나은 경로에 의해 지배된 상태라면 무시 if (dist[c_node][c_cost] < c_time) { continue; } for (const auto& ticket : adjv[c_node]) { int n_node = ticket.to; int n_cost = c_cost + ticket.cost; int n_time = c_time + ticket.time; // 1. 총 비용 초과 시 무시 if (n_cost > M) continue; // 2. 새로 찾은 경로가 기존의 다른 경로에 지배되는지 확인 auto& node_dist_map = dist[n_node]; auto it = node_dist_map.lower_bound(n_cost); // 같은 비용에 더 빠른 경로가 이미 있다면 지배당함 -> 무시 if (it != node_dist_map.end() && it->first == n_cost && it->second <= n_time) { continue; } // 더 적은 비용에 더 빠른 경로가 이미 있다면 지배당함 -> 무시 if (it != node_dist_map.begin() && prev(it)->second <= n_time) { continue; } // 3. 새로운 경로가 기존 경로들을 지배하는지 확인하고, 지배하는 경로들은 삭제 // (더 비싸고, 시간도 더 오래 걸리는 기존 경로들) auto it_to_remove = node_dist_map.lower_bound(n_cost); while (it_to_remove != node_dist_map.end() && it_to_remove->second >= n_time) { it_to_remove = node_dist_map.erase(it_to_remove); } // 4. 지배되지 않는 새로운 경로를 추가하고 큐에 삽입 dist[n_node][n_cost] = n_time; pq.push({n_time, n_node, n_cost}); } } int min_time = INF; // N번 공항에 도착한 경로들 중(모두 non-dominated) 가장 빠른 시간을 찾음 if (dist[N].empty()) { cout << "Poor KCM\n"; } else { for(auto const& [cost, time] : dist[N]) { min_time = min(min_time, time); } cout << min_time << "\n"; } // } return 0; }

제출 #180219

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: