#include #include #include #include using namespace std; typedef pair pii; typedef tuple iii; const int INF = 1e8; int N, M, K; // 공항의 수, 최대 비용, 경로 수 vector> connections; // 연결 정보 {v, c, t} // 비용 내 최단 거리 int traversal(int start, int goal) { // vector> distances(N + 1, vector(M + 1, INF)); // distances[node][cost] = time // distances[start][0] = 0; vector> distances(N + 1); distances[start].emplace_back(0, 0); priority_queue, greater> pq; pq.emplace(0, 0, start); // {시간, 비용, 정점} int v, c, t; // 정점, 비용, 시간 int nv, nc, nt; while (!pq.empty()) { tie(t, c, v) = pq.top(); pq.pop(); for (iii next : connections[v]) { nv = get<0>(next); nc = get<1>(next) + c; nt = get<2>(next) + t; bool isAdded = true; for (auto iter = distances[nv].begin(); iter != distances[nv].end(); iter++) { if (nt <= iter->first && nc <= iter->second) // 좌하단 { distances[nv].erase(iter); iter--; } else if (nt >= iter->first && nc >= iter->second) // 우상단 { isAdded = false; } } // 추가 if (isAdded) { distances[nv].emplace_back(nt, nc); pq.emplace(nt, nc, nv); } /* TODO distances[v] = {{t1, c1}, {t2, c2}, ...} next: {nt, nc} 반복문으로 비교 새로운 것보다 시간과 비용 둘 다 이상인 경우 제거 if (기존 것보다 새로운 것이 둘 다 큰 경우가 존재) 삽입 pii next = {nt, nc}; for (auto iter = distances[v].begin() ; iter != distances[v].end(); iter++) { if (next.first < iter->first && next.second < iter->second) { // next 제거 distances[v].erase(iter); iter--; } } */ } } int answer = INF; for (int i = 0; i < distances[goal].size(); i++) { answer = min(answer, distances[goal][i].first); } return answer; } // 데이터 입력 void inputData() { cin >> N >> M >> K; connections.clear(); connections.resize(N + 1); int u, v, c, d; while (K--) { cin >> u >> v >> c >> d; connections[u].emplace_back(v, c, d); } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T; cin >> T; while (T--) { inputData(); int result = traversal(1, N); if (result == INF) { cout << "Poor KCM"; } else { cout << result; } } }

제출 #115550

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: