글 읽기 - 해당 문제 소스 좀 봐주세요

john6014 8년 전 0

다익스트라를 이용해서 코딩을 했는데 잘못된 부분을 도저히 못 찾겠네요.. 도와주세요 ㅠ

#include <stdio.h>
#include <stdlib.h>
#define INF 1000

int main(void)
{
    int T , N , M;
    int i , j , k;
    int s , t , w;
    int min , index , count = 1; 
    int ** weight;
    int * visit , * parent , * dist , * result;
    
    scanf("%d",&T); // 테스트 케이스 
    for( i = 0 ; i < T; i++)
    {
         scanf("%d %d" , &N , &M); // N : 데이터 입력 개수 , M : 사람 수 
         
         // 다익스트라에 필요한 배열들 동적할당 
         weight = (int**)malloc(sizeof(int*) * M);
         for( j = 0; j < M; j++)
              weight[j] = (int*)malloc(sizeof(int) * M);
              
         parent = (int*)malloc(sizeof(int) * M);
         dist = (int*)malloc(sizeof(int) * M);
         result = (int*)malloc(sizeof(int) * M);
         visit = (int*)malloc(sizeof(int) * M);
         
         // 배열 초기화 
         for ( j = 0; j < M; j++)
         {
             for( k = 0; k < M; k++)
                  weight[j][k] = INF;
             
             visit[j] = result[j] = -1; 
         } 
         
         // 데이터 입력 
         for(j = 0; j < N; j++)
         {
               scanf("%d %d %d",&s,&t,&w);
               weight[s][t] = w;
         }
         
         // dist 배열 초기화 
         for( j = 0; j < M; j++)
         {
              dist[j] = weight[0][j];
              
              if ( weight[0][j] != INF )
                 parent[j] = 0;
              else
                 parent[j] = -1;
         }
         
         // 다익스트라 알고리즘
         dist[0] = 0;        // 시작점의 거리 0
 	     visit[0] = 1;

        for ( j = 0; j < M; j++)
        {
                index = -1;
                min = INF;
               
                for ( k = 0 ; k < M; k++)
                {
                        if ( visit[k] == -1 && min > dist[k])    // 갈수 있는 정점중에 가장 가까운 정점 선택
                        {
                                min = dist[k];
                                index = k;
                        }
                }
                
                if ( index == -1 )
                    continue;
                else
                    visit[index] = 1;
       
                for ( k = 0;k < M; k++)      
                {
                        if ( visit[k] == -1 && dist[k] > dist[index] + weight[index][k])
                        {       
                                dist[k] = dist[index] + weight[index][k];
                                parent[k] = index;
                        }
                }
        } 
      
        // 출력
        j = M - 1; // 도착점
        k = 0;
        
        if ( parent[j] == -1 )
           printf("Case #%d: -1\n",count);
        else
        {
            while( 1 )
            {
                result[k++] = j;
                j = parent[j];
                
                if(parent[j] == -1)
                   break;   
            }
       
            printf("Case #%d: 0 ",count);
            
            for( j = k - 1; j >= 0; j--)
                 printf("%d ",result[j]);
                 
            printf("\n");
        }
        
        // 동적할당 해제 
        free(result);    free(dist);
        free(visit);     free(parent);
        
        for( j = 0; j < M; j++)          
             free(weight[j]);
        
        free(weight);
        
        count++;
    }
    
    //system("pause");
    
    return 0;
}

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

문제

문제

출처

ICPC

해당 문제 소스 좀 봐주세요

john6014 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말