Chuyến bay bầu cử

Points: 4

Time limit: 1.0s

Memory limit: 256M

Author:

Problem types

Allowed languages

Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, ~~GAS32~~, GO, Haskell, Itercal, Java, kotlin, ~~LEAN~~, LISP, LUA, MONOVB, ~~Nasm~~, ~~OCAML~~, Pascal, Perl, php, PIKE, ~~prolog~~, Pypy, Python, ~~Ruby 2~~, RUST, Scala, SCM, SED, ~~SWIFT~~, TCL, ~~TUR~~, ~~V8JS~~, VB, ZIG

Sắp tới đây bạn được đại diện cho Việt Nam đi tham gia bầu cử chủ tịch Liên Hợp Quốc

Bạn sẽ đi từ Việt Nam đến Mỹ bằng máy bay, bạn muốn tìm câu trả lời cho những câu hỏi sau:

$1$ . Giá tối thiểu của một tuyến đường như vậy là gì?

$2$ . Có bao nhiêu tuyến đường giá tối thiểu?

$3$ . Số lượng chuyến bay tối thiểu với tuyến giá tối thiểu là bao nhiêu?

$4$ . Số lượng chuyến bay tối đa với tuyến giá tối thiểu là bao nhiêu?

Đầu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ , số quốc gia và số chuyến bay. Các quốc gia được đánh số $1, 2, \dots, n$ . Quốc gia $1$ là Việt Nam, và Quốc gia $n$ là Mỹ.

Tiếp theo, có $m$ dòng mô tả các chuyến bay. Mỗi dòng chứa ba số nguyên $a, b, c$ : có một chuyến bay từ quốc gia $a$ đến quốc gia $b$ với giá $c$ . Tất cả các chuyến bay đều là chuyến bay một chiều.

Đầu ra

Bốn số nguyên theo những câu hỏi trên lấy dư $1000000007$ .

Giới hạn

$1 \leq n \leq 10^{5}$

$1 \leq m \leq 2 * 10^{5}$

$1 \leq a, b \leq n$

$1 \leq c \leq 10^{9}$

Ví dụ:

Đầu vào:

Copy

Đầu ra:

Copy

5 2 1 2

Comments

0

hungdzvcl commented on Oct. 23, 2024, 3:37 p.m.

Đề bảo lấy dư 1e9+7 mà giá tối thiểu chia MOD lại sai =)))