[백준] 14284 간선 이어가기 2, python, C++

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

14284번: 간선 이어가기 2

이 문제는 s에서 출발해서 t까지의 최소 가중치를 구하는 문제이다.

다익스트라를 사용하면 쉽게 구할 수 있다.

 

 

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define INF 1234567890

int dijkstra(int start, int end, int size, vector<vector<pair<int, int>>> linked_list) {
	int cur, cur_dist, adj, adj_dist, i;
	priority_queue<pair<int, int>> min_h;
	vector<int> visit(size + 1, INF);
	min_h.push(make_pair(0, start));
	while (!min_h.empty())
	{
		cur_dist = -min_h.top().first;
		cur = min_h.top().second;
		min_h.pop();
		if (cur == end)
			return cur_dist;
		visit[cur] = cur_dist;
		for (i = 0; i < linked_list[cur].size(); i++)
		{
			adj_dist = linked_list[cur][i].first;
			adj = linked_list[cur][i].second;
			if (visit[adj] > adj_dist + cur_dist) {
				min_h.push(make_pair(-(adj_dist + cur_dist), adj));
			}
		}
	}
	return INF;
}


int main()
{
	//ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, a, b, c, s, t, i, j;
	cin >> n >> m;
	vector<vector<pair<int, int>>> linked_list(n + 1);
	for (i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		linked_list[a].push_back(make_pair(c, b));
		linked_list[b].push_back(make_pair(c, a));
	}
	cin >> s >> t;

	cout << dijkstra(s, t, n, linked_list) << '\n';

	return 0;
}

# import sys; input = sys.stdin.readline
from heapq import heappop, heappush
INF = 1234567890
def dijkstra(s, e, size, linked_list):
    h = [(0, s)]
    dist = [INF for _ in range(size + 1)]
    while h:
        cur_dist, cur = heappop(h)
        if cur == e:
            return cur_dist
        dist[cur] = cur_dist
        for adj_dist, adj in linked_list[cur]:
            if dist[adj] > cur_dist + adj_dist:
                heappush(h, (cur_dist + adj_dist, adj))
    return INF


def main():
    N, M = map(int, input().split())
    linked_list = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        linked_list[a].append((c, b))
        linked_list[b].append((c, a))
    s, t = map(int, input().split())

    return dijkstra(s, t, N, linked_list)

if __name__ == "__main__":
    print(main())

C++이랑 python이랑 알고리즘은 똑같지만 stl에 익숙해지기 위해 사용했다.