[8일차][다익스트라] 최단거리

- 문제 설명

0->N번 노드로 가는 최소비용 거리 

- 입력

1 // 테스트 케이스

2 3 // N, 엣지갯수

0 1 1 // 0~1로 가는데 비용 1

0 2 1 // 0~2로 가는데 비용 1

1 2 6 // 1~2로 가는데 비용 6

- 출력

#1 1 // 테스트케이스, 비용 1(0~2로 한번에 가면 되기 때문)

- 입력 예시

3
2 3
0 1 1
0 2 1
1 2 6
4 7
0 1 9
0 2 3
0 3 7
1 4 2
2 3 8
2 4 1
3 4 8
4 6
0 1 10
0 2 7
1 4 2
2 3 10
2 4 3
3 4 10

- 출력 예시

#1 1
#2 4
#3 10

- 코드 

#include "stdio.h"

int N, E;

int map[1001][1001];

int distance[1001];

int used[1001];

void dijkstra();

#define INF 0x7ffffff

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        scanf("%d %d",&N,&E);

        for (int i = 0; i<=N;i++)

        {

            distance[i] = 0; // distance값 초기화

            used[i] = 0; // used 값 초기화

            for(int j=0;j<=N;j++)

            {

                if(i==j)

                    map[i][j] =0; // 자기 자신은 0

                else

                    map[i][j] = INF; // 기본적으로 무한대

            }

        }

        for (int i = 1; i<=E;i++) // 엣지 갯수 만큼

        {

            int n1, n2, w;

            scanf("%d %d %d",&n1,&n2,&w);

            map[n1][n2] = w; // 갈 수 있는 비용 입력

        }

        dijkstra();

        printf("#%d %d\n", tc,distance[N]); // 마지막 노드의 비용 출력

    }

    return 0;

}

void dijkstra()

{

    for(int i = 0;i<=N;i++)

    {

        distance[i] = map[0][i]; // distance 배열 얻어오기, 0번노드에서 출발하기 때문에 map[0]을 가져옴

    }

 

    used[0] = 1; // 0번노드에서 시작하므로 1로 초기화

    int count = 0; // 0번부터 시작

    while(count < N)

    {

        //used[t]가 0이고(아직 가지 않았고), distance[t]가 최소인 t찾기

        int t = 0;

        int min = INF;

        for(int i=0;i<=N;i++)

        {

            if(used[i] == 0 && distance[i] < min) // 아직 해당 노드를 지나지 않았고, 노드로 갈 수 있는 최소 거리인 경우

            {

                min = distance[i]; // 최소값 저장

                t = i; // 최소값의 인덱스를 저장

            }

        }

        used[t] = 1; // 경유지 표시

        // t를 경유지로, t에서 갈 수 있는 모든 노드 조사

        for(int i=0;i<=N;i++)

        {

            if(map[t][i] != 0 && map[t][i] != INF) // 0도아니고 무한대도 아니고, 즉 갈 수 있는 곳이면

            {

                // 만약 현재 저장된 거리보다 더 작은 값이 들어온다면 그 값을 저장

                distance[i] = (distance[i] < distance[t] + map[t][i]) ? distance[i] : distance[t] + map[t][i];

            }

        }

        count++; // 카운트 증가

    }

}