Đường Đi Ngắn Nhất I

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ thành phố và $m$ tuyến bay một chiều. Tìm độ dài đường đi ngắn nhất từ thành phố $1$ đến tất cả các thành phố còn lại.

Dòng 1: hai số nguyên $n$ và $m$ .
$m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $a$ , $b$ , $c$ — tuyến bay từ $a$ đến $b$ với độ dài $c$ .

In $n$ số nguyên — khoảng cách ngắn nhất từ thành phố $1$ đến từng thành phố $1, 2, \dots, n$ .

Input	Output	Giải thích
3 4 1 2 6 1 3 2 3 2 3 1 3 4	0 5 2	Đến 2: qua 3 (2+3=5); đến 3: trực tiếp (2).
4 5 1 2 3 1 3 8 2 4 1 3 4 2 2 3 4	0 3 7 4	Dijkstra từ đỉnh 1.

Bình luận

Không có bình luận tại thời điểm này.