Điều Tra

Đ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$ chuyến bay một chiều. Tìm bốn thông tin về đường đi từ thành phố $1$ đến thành phố $n$ : (1) chi phí nhỏ nhất, (2) số đường đi có chi phí nhỏ nhất (modulo $10^{9} + 7$ ), (3) số chuyến bay ít nhất trong một đường đi tối ưu, (4) số chuyến bay nhiều nhất trong một đường đi tối ưu.

Dữ liệu vào

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$ — chuyến bay từ $a$ đến $b$ với chi phí $c$ .

Dữ liệu ra

In bốn số nguyên trên một dòng.

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq m \leq 2 \times 10^{5}$
$1 \leq c \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 5 1 4 5 1 2 4 2 4 5 1 3 2 3 4 3	5 2 1 2	Chi phí min=5 (đường 1→4 và 1→3→4), 2 đường, min 1 chuyến, max 2 chuyến.

Bình luận

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