글 읽기 - [c++] 다익스트라/왜 inf + 1로 초기화해줘야 하나요?

gyenari00 3년 전 1

아래 소스는 맞았습니다를 받은 소스입니다. 궁금했던건

31번째 줄을

m = inf; 로 고치면 왜 틀리는 걸까요?

인접리스트를 이용했고 다익스트라 O(V^2) 방식을 이용했습니다. 즉 priority queue를 사용안하고 매번 정점을 하나하나 탐색하면서 거리가 최소인 정점을 찾아 방문하는 알고리즘입니다.

31번째 줄 부분은 거리가 최소인 정점을 찾는 부분인데

m = inf; 이어야 하지 않나요? ㅠㅜㅠ

왜냐면 남은 모든 정점까지의 거리가 inf일 경우 이제 더이상 닿을 수 있는 정점이 없으니 종료해야 할 것같은데

m = inf + 1; 로 해주게 되면 종료를 안하게 되니까 틀릴것같은데 이해가 안됩니다....

질문 읽어주셔서 감사합니다.

#include <cstdio>
#include <vector>
using namespace std;
struct Edge {
    int to;
    int cost;
    Edge(int to, int cost) : to(to), cost(cost) {
    }
};
vector<Edge> a[1001];
int dist[1001];
bool check[1001];
int inf = 1000000000;
int main() {
    int n;
    scanf("%d",&n);
    int m;
    scanf("%d",&m);
    for (int i=0; i<m; i++) {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        a[x].push_back(Edge(y,z));
    }
    int start, end;
    scanf("%d %d",&start,&end);
    for (int i=1; i<=n; i++) {
        dist[i] = inf;
    }
    dist[start] = 0;
    for (int k=0; k<n-1; k++) {
        int m = inf+1;
        int x = -1;
        for (int i=1; i<=n; i++) {
            if (check[i] == false && m > dist[i]) {
                m = dist[i];
                x = i;
            }
        }
        check[x] = true;
        for (int i=0; i<a[x].size(); i++) {
            int y = a[x][i].to;
            if (dist[y] > dist[x] + a[x][i].cost) {
                dist[y] = dist[x] + a[x][i].cost;
            }
        }
    }
    printf("%d\n",dist[end]);
    return 0;
}

mc_progw12 3년 전 0

inf값이 10억이라면, 34행에서 dist[i]가 모두 10억(최대 10억)일 때? 34행이 실행되지 않아(x 값이 산정되지 않아) 문제가 생기는 것 아닐까요?

cutecjh33 3년 전 0

dist[start] = 0이라 34행이 실행되지 않는 경우는 없습니다.

저도 같은 문제를 고민중인데 도무지 모르겠네요

왜 INF 보다 큰 값으로 해야만 하는건지...

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

문제

문제

출처

ICPC

[c++] 다익스트라/왜 inf + 1로 초기화해줘야 하나요?

gyenari00 3년 전 1

mc_progw12 3년 전 0

cutecjh33 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말