#include <stdio.h> const int inf=2147483647; int airportnum, maxmoney, airlinenum; int airline[10005][4] = {0}; // 0 start, 1 arrive, 2 money, 3 time int searching[105]={0}; int airportstart[105]={0}; // airportline start int minimumdrive[105][2]={0}; // minimum arrive, 0 money 1 time void swap(int l, int r){ int i, temp; for(i=0; i<4; i++){ temp = airline[l][i]; airline[l][i] = airline[r][i]; airline[r][i] = temp; } } void partquick(int l, int r){ int ll, rr, temp, target; ll=l; rr=r; target=(l+r)/2; if(l==r) return; else if(l==r-1){ if(airline[l][0] > airline[r][0]) swap(l,r); return; } while(1){ while( airline[l][0] <= airline[target][0] && l<target) l++; while( airline[r][0] >= airline[target][0] && r>target) r--; if(l==r) break; swap(l, r); if(l==target) target = r; else if(target==r) target = l; } if(ll!=target) partquick(ll, target-1); if(rr!=target) partquick(target+1, rr); } int search(int start, int nowtime, int nowmoney){ // now time and money spent, and start to next, return time; int i, mintime=inf, temp; if(searching[start]==1) return -1; searching[start]=1; if(minimumdrive[start][0]==0 && minimumdrive[start][1]==0){ minimumdrive[start][0] = nowmoney; minimumdrive[start][1] = nowtime; } else if(minimumdrive[start][1] <= nowtime){ searching[start]=0; return -1; } else if(minimumdrive[start][1] >= nowtime){ minimumdrive[start][0] = nowmoney; minimumdrive[start][1] = nowtime; } //printf("MM(%d) : %d %d\n", start, minimumdrive[start][0], minimumdrive[start][1]); //printf("SEARCHING from %d, nowtime %d, nowmoney %d\n", start, nowtime, nowmoney); if(start==airportnum){ //printf("ARRIVED : time %d\n", nowtime); searching[start]=0; return nowtime; } for(i=airportstart[start]; airline[i][0]==start; i++){ //printf("%d->%d, money %d, time %d\n", airline[i][0], airline[i][1], airline[i][2], airline[i][3]); if(nowmoney+airline[i][2] <= maxmoney){ temp = search(airline[i][1], nowtime+airline[i][3], nowmoney+airline[i][2]); if(temp!=-1 && temp < mintime) mintime = temp; //printf("SearchResult : %d\n", temp); } //printf("\n"); } //printf("SEARCHING from %d ? MINTIME %d, so return time %d\n", start, mintime, mintime+nowtime); searching[start]=0; if(mintime==inf || mintime<0) return -1; return mintime; } int main(void){ int testcase, answer; int i, j, temp; scanf("%d", &testcase); while(testcase>0){ for(i=0; i<105; i++){ airportstart[i]=0; searching[i]=0; minimumdrive[i][0]=0; minimumdrive[i][1]=0; } scanf("%d %d %d", &airportnum, &maxmoney, &airlinenum); for(i=1; i<airlinenum+1; i++){ scanf("%d %d %d %d", &airline[i][0], &airline[i][1], &airline[i][2], &airline[i][3]); } airline[i][0]=0, airline[i][1]=0, airline[i][2]=0, airline[i][3]=0; partquick(1, airlinenum); for(i=1; i<airlinenum+1; i++){ //printf("%d->%d, money %d, time %d\n", airline[i][0], airline[i][1], airline[i][2], airline[i][3]); } //printf("\n"); temp=0; for(i=1; i<airlinenum+1; i++){ if(temp!=airline[i][0]){ temp = airline[i][0]; airportstart[temp] = i; } } //for(i=1; i<=airlinenum; i++){ // printf("%d %d %d %d\n", airline[i][0], airline[i][1], airline[i][2], airline[i][3]); //} //searchstacknum=0; //for(i=airportstart[1]; airline[i][0]==airportstart[1]; i++){ // searchstack[temp] = i; // searchstacknum++; //} answer = search(1, 0, 0); if(answer==-1) printf("Poor KCM\n"); else printf("%d\n", answer); testcase--; } } 여기서 search 함수에서 minimumdrive[start][1] (시간) 만 비교하고도 바로 탐색을 중단하게 시켰는데, 이게 왜 맞는 코드인가요? 시간이 더 짧더라도, 비용이 중간에 초과되서 탐색을 멈춰야 하는 경우가 있을 것 같은데..

...뭐지이건ㅋㅋㅋ왜 남의 사이트 문제를 여기서 물어봨ㅋㅋㅋ 그러게.. 실제로 1 5 5 4 1 2 2 1 2 3 2 1 3 5 2 1 1 3 1 5 이 데이터를 넣으면 6이 아니라 Poor KCM을 출력하고있네.... 백준옹께 문의해보마

이미 의문은 해결했어요~ 이건 잘못된거고, 다익스트라를 좀 응용시켜야 한다는데 ㅋㅋㅋ 하 알고RI즘.. 제가 알고리즘을 배우지 않고도, 그냥 스스로 생각해서 풀고 싶은데 그게 정말 힘드네요 ㅋㅋㅋ