글 읽기 - 어느 부분이 틀린 걸까요...?

blackout 4년 전 0

다익스트라 초보라서 어디가 틀린건지 모르겠네요...

어디가 틀린거죠...?

#include <stdio.h>
#define MAX 1010
#define INF 100000000
int grp[MAX][MAX];
int dst[MAX];
int visit[MAX];
int main()
{
    int n,m,k,e;
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        grp[u][v]=(grp[u][v]==0)? w:((w<grp[u][v])? w:grp[u][v]);
    }
    scanf("%d %d",&k,&e);
    for(int i=1;i<=n;i++){
        if(k==i) dst[i]=0;
        else if(grp[k][i]==0) dst[i]=INF;
        else dst[i]=grp[k][i];
    }
    for(int i=0;i<n;i++){
        int sm=INF;
        int v;
        for(int j=1;j<=n;j++){
            if(visit[j]==0 && sm>dst[j]){
                sm=dst[j];
                v=j;
            }
        }
        visit[v]=1;
        for(int j=1;j<=n;j++){
            if(grp[v][j]!=0 && j!=v && j!=k){
                if(dst[j]>dst[v]+grp[v][j]){
                    dst[j]=dst[v]+grp[v][j];
                }
            }
        }
    }
    printf("%d\n",dst[e]);
    return 0;
}

djm03178 4년 전 0

"버스 비용은 0보다 크거나 같고"
도착점을 갈 수 있다고 했지, 도착점 이외의 장소도 모두 갈 수 있다는 조건은 없습니다. 이 경우 29번째 줄이 한 번도 실행되지 않는 경우가 생기게 되고 이후의 동작은 무슨 일이 일어날지 알 수 없게 됩니다.

blackout 4년 전 0

아 이 코드가 다른 문제 코드에서 변형한 건데 그래서 조건을 제데로 읽어보지 못한 거였네요...

감사합니다!

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

문제

문제

출처

ICPC

어느 부분이 틀린 걸까요...?

blackout 4년 전 0

djm03178 4년 전 0

blackout 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말