LOJ119 - Đường đi ngắn nhất
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, JavaScript, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho một đồ thị vô hướng có ~n(1 \leq n \leq 2500)~ đỉnh và ~m(1 \leq m \leq 6200)~ cạnh, hãy tìm đường đi ngắn nhất từ ~s~ đến ~t~.
Input
- Dòng đầu tiên chứa bốn số nguyên ~n, m, s, t~ cách nhau bởi dấu cách.
- ~m~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương ~s_i, t_i, w_i (1 \leq w_i \leq 10^9)~ là cạnh từ ~s_i~ đến ~t_i~ có độ dài ~w_i~.
Output
Một số nguyên đại diện cho độ dài của con đường ngắn nhất từ ~s~ đến ~t~. Dữ liệu đảm bảo rằng tồn tại ít nhất một đường đi.
Sample
Input #1
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
Output #1
7
Bình luận
from heapq import heappop, heappush from collections import defaultdict n, m, s, t = map(int, input().split()) adj = defaultdict(list) for _ in range(m): u, v, w = map(int, input().split()) adj[u].append((v, w)) adj[v].append((u, w)) INF = 10**18 dist = [INF] * (n + 1) dist[s] = 0 pq = [(0, s)] while pq: d, u = heappop(pq) if d > dist[u]: continue for v, w in adj[u]: if dist[u] + w < dist[v]: dist[v] = dist[u] + w heappush(pq, (dist[v], v)) print(dist[t])