최단 경로 - 다익스트라 - dijkstra

이코테 - 최단경로 

 

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int n, m, start;
vector<pair<int, int>> graph[100001];
bool visited[100001];
int d[100001];

int getSmallestNode(){
    int min_value = INF;
    int index = 0;
    for(int i=1; i<=n; i++){
        if(d[i] < min_value && !visited[i]){
            min_value = d[i];
            index = i;
        }
    }
    return index;
}

void dijkstra(int start){
    d[start] = 0;
    visited[start] = true;
    for(int j=0; j<graph[start].size(); j++){
        d[graph[start][j].first] = graph[start][j].second;
    }

    for(int i=0; i<n-1; i++){
        int now = getSmallestNode();
        visited[now] = true;
        for(int j=0; j<graph[now].size(); j++){
            int cost_via_now = d[now] + graph[now][j].second;
            if(cost_via_now < d[graph[now][j].first]){
                d[graph[now][j].first] = cost_via_now;
            }
        }
    }
}


int main()
{
    cin >> n >> m >> start;

    for(int i=0; i<m; i++){
        int a, b, c;
        cin >> a >> b >>c;
        graph[a].push_back({b,c});
    }

    fill_n(d, 100001, INF);

    dijkstra(start);

    for(int i=1; i<=n; i++){
        if(d[i] == INF){
            cout << "INFINITY" << "\n";
        }
        else{
            cout << d[i] << "\n";
        }

    }
    return 0;
}


/*
입력 예시
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
*/