Đường đi ngắn nhất (Dijkstra)

Khó

đồ thịDijkstraheap5 test · 3 giây

Đồ thị vô hướng có n đỉnh và m cạnh có trọng số dương. Tính độ dài đường đi ngắn nhất từ đỉnh 1 tới mọi đỉnh. Đỉnh không tới được in -1.

Trọng số khác nhau nên BFS không đúng. Dùng Dijkstra với hàng đợi ưu tiên → O((n + m) log n).

Dữ liệu vào

Dòng 1: n m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2·10⁵).

m dòng: u v w (1 ≤ w ≤ 10⁹).

Một dòng gồm n số: khoảng cách tới đỉnh 1, 2, …, n (có thể vượt 32-bit).

Input

Output

0 3 1 8 11

1 → 3 → 2 dài 3, ngắn hơn cạnh trực tiếp 1 → 2 (dài 4)

Input

3 1
1 2 7

Output

0 7 -1

Đỉnh 3 không tới được

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.