글 읽기 - 1162번 도로포장 문제 런타임 에러 (반례 하나만 부탁드려요)

cnh2769 7년 전 0

안녕하세요~

이제 막 백준 맛들린 신참입니다.

도로포장 문제가 자꾸 런타임에러가 뜨는데 이유를 도무지 모르겠네요.....ㅠㅠ

for문은 아무리 찾아봐도 문제가 없고,

아마도, bfs 할 때 Q.push(...) 가 무한히 일어나는 경우가 있나...? 싶은데

그런 예가 어떤 경우가 있는지를 못찾겠습니다...

isVisited를 무시하기위해 추가한 isDevine 플래그에 약점이 있을까요?

혹시 런타임 에러가 날만한 샘플이 있으면 부탁드리겠습니다.

#include <stdio.h>
#include <queue>
#include <vector>
#include <functional>
 
using namespace std;
 
typedef struct Way {
    int dst;
    long long int cost;
} Way;
 
typedef struct Node {
    int v;
    int usedK;
    long long int totalCost;
    bool isDevine;
    Node(int _v, int _usedK, long long int _totalCost, bool _isDevine) {
        v = _v;
        usedK = _usedK;
        totalCost = _totalCost;
        isDevine = _isDevine;
    }
    bool operator > (const Node& a) const {
        return totalCost > a.totalCost;
    }
} Node;
 
int N, M, K;
int src, dst;
long long int cost;
 
//vector<bool> isVisited;
bool isVisited[10001];
vector<vector<Way>> W;
 
int main()
{
    Way w;
    vector<Way> dummy;
 
    scanf("%d %d %d", &N, &M, &K);
    W.assign(N + 1, dummy);
    //isVisited.assign(N + 1, false);
    for (int i = 0; i < M; i++) {
        scanf("%d %d %lld", &src, &dst, &cost);
        w.dst = dst; w.cost = cost;
        W[src].push_back(w);
        w.dst = src; w.cost = cost;
        W[dst].push_back(w);
    }
 
    priority_queue<Node, vector<Node>, greater<Node>> Q;
    Node q(1, 0, 0, false);
    Q.push(q);
 
    while (!Q.empty()) {
        q = Q.top();
        Q.pop();
        src = q.v;
 
        if (q.v == N) {
            printf("%lld\n", q.totalCost);
            break;
        }
 
        if (!q.isDevine) {
            if (isVisited[q.v]) continue;
            else isVisited[q.v] = true;
        }
 
        for (int i = 0; i < W[src].size(); i++) {
            if (!isVisited[W[src][i].dst]) {
                Q.push(Node(W[src][i].dst, q.usedK, q.totalCost + W[src][i].cost, false));
                if (q.usedK < K) {
                    Q.push(Node(W[src][i].dst, q.usedK + 1, q.totalCost, true));
                }
            }
        }
    }
}

edlsw 3년 전 0

2 2 1

1 2 10

2 1 51

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

문제

문제

출처

ICPC

1162번 도로포장 문제 런타임 에러 (반례 하나만 부탁드려요)

cnh2769 7년 전 0

edlsw 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말