글 읽기 - 도와주세요 ㅜㅜ

seonh4996 4년 전 0

왜 틀리는지 모르겠어요..

dp로 안풀어서 시간초과면 납득하는데.. 틀렸다고 나오니 답답하네요 ㅜㅜ

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using point = pair<int,int>;
using pip = pair<int, point>;



int limit=987654321;
int T,N,M,K;

pip make_three(int a,int b, int c){
	return make_pair(a,make_pair(b,c));
}

void dijkstra(vector<vector<pip> > tickets){
	
	vector<point> limit_times_money(101,make_pair(limit,0));
	limit_times_money[1].first = 0;
	priority_queue<pip> pq;
	// 시간 돈 번호 순서
	pq.push(make_three(0,0,1));
	
	while(!pq.empty()){
		int num = pq.top().second.second;
		int time = -pq.top().first;
		int money = pq.top().second.first;
		pq.pop();
		
		if(time > limit_times_money[num].first)continue;
		
		for(int i = 0; i < tickets[num].size(); i++){
			int nextnum = tickets[num][i].first;
			int nexttime = tickets[num][i].second.second + time;
			int nextmoney = tickets[num][i].second.first + money;
			
			if(nextmoney > N) continue;
			if(nexttime < limit_times_money[nextnum].first){
				limit_times_money[nextnum].first = nexttime;
				limit_times_money[nextnum].second = nextmoney;
				pq.push(make_three(-nexttime,nextmoney,nextnum));
			}
			
			
		}
		
	}
	
	if(limit_times_money[N].first >= limit)cout << "Poor KCM" << '\n';
	else cout << limit_times_money[N].first << '\n';
	
	
}

int main(){
	cin.tie(0);
	ios_base :: sync_with_stdio(0);
	
	cin >> T;
	
	while(T--){
		cin >> N >> M >> K;
		vector<vector<pip> > tickets(101,vector<pip>());
		for(int i = 0; i < K; i++){
			int a,b,c,d;
			cin >> a >> b >> c >> d;
			tickets[a].push_back(make_three(b,c,d));
		}
		
		dijkstra(tickets);
		
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

도와주세요 ㅜㅜ

seonh4996 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말