문제 1753. 최단경로(에센셜 4)

문제 링크

https://www.acmicpc.net/problem/1753

 

난이도 :  골드 4

 

문제 요약 설명

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E

둘째 줄에는 시작 정점의 번호 K

셋째 줄부터 E개의 줄: 각 간선을 나타내는 세 개의 정수 (u, v, w)이 주어진다. ( u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻 )

입력 제한

정점의 개수 V  (1 ≤ V ≤ 20,000)

간선의 개수 E (1 ≤ E ≤ 300,000)

시작 정점의 번호 K (1 ≤ K ≤ V)

u와 v는 서로 다르며 w는 10 이하의 자연수이다.

서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있다.

입력 예제

// input
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

// ans
0
2
3
7
INF

 

풀이 방식

다익스트라 알고리즘 사용.

 

정답 코드 

#include <bits/stdc++.h>

#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

struct path_data
{
    int node_no;
    int distance;
};

struct edge_data
{
    int node_no;
    int weight;
};

struct cmp
{
    bool operator()(const path_data& a, const path_data& b){
        return a.distance > b.distance;
    }
};

int V, E, K; 
vector<vector<edge_data>> graph;

vector<int> dijkstra_algorithm(int start_node_no){

    priority_queue<path_data, vector<path_data>, cmp> pq;
    vector<int> shortest_dist(V+1, INT32_MAX);

    // init
    for(edge_data ed : graph[start_node_no]){
        pq.push({ed.node_no, ed.weight});
        shortest_dist[ed.node_no] = ed.weight;
    }

    while(!pq.empty()){
        path_data cur_path = pq.top(); pq.pop();

        for(edge_data ed : graph[cur_path.node_no]){

            int Next_node = ed.node_no;
            int nDist = cur_path.distance + ed.weight;
            
            if(nDist < shortest_dist[Next_node]){
                shortest_dist[ed.node_no] = nDist;
                pq.push({ed.node_no, nDist});        
            }
        }

    }

    return shortest_dist;
}

int main() {
	fastio;
    cin >> V >> E >> K;

    graph.resize(V+1);

    int node1, node2, weight;
    graph[K].push_back({K, 0});
    for(int i = 0; i < E; i++){
        cin >> node1 >> node2 >> weight;
        graph[node1].push_back({node2, weight});
    }  
    
    vector<int> ans;
    ans = dijkstra_algorithm(K);

    for(int i = 1; i<=V; i++){
        if(ans[i] == INT32_MAX){
            cout << "INF" << '\n';
        }
        else{
            cout << ans[i] << '\n';
        }
        
    }

}

 

더 좋은 코드?

우선순위 큐를 쓸 때에는 비교함수를 최대한 사용하지 않는 것이 좋다. 비교함수를 사용자가 정의하게 될 경우, 실행속도가 대폭 느려진다. 위에 있는 내 코드는 실행속도가 700~900ms 정도 나오는데, 이는 다른 제출자가 100ms 내외 인 것을 보면 알 수 있다.(해당 제출자들은 비교함수를 정의하지 않고 코드를 짰다). 더 좋은 코드를 짜고 싶다면 가독성을 해치지 않는 선에서 우선순위 큐에 비교함수를 재정의 하지않는 방법을 고려해봐야 한다.

참고