글 읽기 - 도와주세요 !

cocogod 7년 전 0

우선순위 큐에 정렬은 돈이 적은순으로 정렬합니다.

이제 다익스트라를 이용하여 돈이 총합보다 적고 총시간보다 적고 적은 돈을

우선순위 큐에 넣으며 확인하였습니다.

반례좀 찾아주세요 ㅠㅠ

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>

using namespace std;
#define INF 1000000000
struct road {
    int end;
    int money;
    int time;
};


struct cmp {
    bool operator()(road a,road b){
        return a.money > b.money;
    }
};

int main(){
    int n,T,M,l;
    
    vector<road > v[101];
    int d[101][2];
    int visited[101];
    for(int i=0;i<101;i++){
        d[i][0] = d[i][1] = INF;
        visited[i] = 0;
    }
    
    
    scanf("%d %d %d %d",&n,&T,&M,&l);
    for(int i=0;i<l;i++){
        int start,end,tt,mm;
        scanf("%d %d %d %d",&start,&end,&tt,&mm);
        road temp ;
        temp.end = end; temp.time = tt; temp.money = mm;
        v[start].push_back(temp);
        temp.end = start;
        v[end].push_back(temp);
    }
    
    priority_queue<road, vector<road >, cmp > pq;
    road tmp; tmp.end =1; tmp.money=0; tmp.time=0;
    pq.push(tmp);
    d[1][0] = d[1][1] = 0; //0번돈 1시간
    while(!pq.empty()){
        int k = pq.top().end;
        pq.pop();
        
        if(visited[k])
            continue;
        visited[k] = 1;
        
        int siz = v[k].size();
        for(int i=0;i<siz;i++){
            int there = v[k][i].end;
            int money = v[k][i].money;
            int time = v[k][i].time;
            // 다음으로 갈곳이 총 돈보다 적고 총시간본다 적으면 queue에 넣음
            if(d[there][0] > d[k][0]+money && d[k][0]+money <= M && d[k][1] + time <= T){
                d[there][0] = d[k][0]+money;
                d[there][1] = d[k][1]+time;
                road temp; temp.end = there; temp.money = d[there][0]; temp.time = d[there][1];
                pq.push(temp);
            }
        }
        
        
    }
    
    printf("%d\n",d[n][0] ==INF ? -1 : d[n][0]);
    
    
}

qja0950 7년 전 0

지금 사용한 돈을 기준으로 작은 순서대로 우선순위 큐를 사용하셨는데,

사용한 돈이 적지만 시간이 오래걸리는 경우 vs 사용한 돈이 조금 더 많지만 시간이 적게 걸리는 경우

이 두 경우에서 후자만 문제 조건에 맞는 경로가 될 수 있습니다.

100 100

1 2 99 99

1 2 100 1

2 3 1 1

이 경우가 반례가 되네요.

100이 나와야하는데 -1이 나옵니다.

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

문제

문제

출처

ICPC

도와주세요 !

cocogod 7년 전 0

qja0950 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말