Đồ thị 02: Dijkstra

Có \(n\) thành phố và \(m\) chuyến bay giữa chúng. Nhiệm vụ của bạn là xác định độ dài của tuyến đường ngắn nhất từ ​​Syrjälä đến mọi thành phố.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng thành phố và chuyến bay. Các thành phố được đánh số \(1,2,\ldots,n\) và thành phố \(1\) là Syrjälä.
• Sau đó, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(c\): một chuyến bay bắt đầu tại thành phố \(a\), kết thúc tại thành phố \(b\), và độ dài của nó là \(c\). Mỗi chuyến bay là một chuyến bay một chiều.
• Bạn có thể giả định rằng có thể đi từ Syrjälä đến tất cả các thành phố khác.

Constraints

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)
• \(1 \leq c \leq 10^9\)

Output

• In \(n\) số nguyên: độ dài tuyến đường ngắn nhất từ ​​Syrjälä đến các thành phố \(1,2,\ldots,n\).

Example

3 4
1 2 6
1 3 2
3 2 3
1 3 4

0 5 2

Nhiệm vụ của bạn là tìm một lộ trình bay rẻ nhất từ Syrjälä đến Metsälä. Bạn có một phiếu khuyến mãi, sử dụng nó có thể giảm một nửa giá của bất kỳ chuyến bay nào trong suốt lộ trình. Tuy nhiên, bạn chỉ có thể sử dụng phiếu đó một lần.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng thành phố và chuyến bay. Các thành phố được đánh số \(1, 2, \ldots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Metsälä.
• Sau này, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\) và \(c\): một chuyến bay bắt đầu tại thành phố \(a\), kết thúc tại thành phố \(b\), và giá của nó là \(c\). Mỗi chuyến bay đều là một chiều.
• Bạn có thể giả định rằng luôn luôn có thể đi từ Syrjälä đến Metsälä.

Output

• In một số nguyên: giá của lộ trình rẻ nhất từ Syrjälä đến Metsälä.
• Khi bạn sử dụng phiếu khuyến mãi cho một chuyến bay mà giá tiền của nó là \(x\), giá tiền của nó trở thành \(\lfloor x/2 \rfloor\) (làm tròn xuống một số nguyên).

Constraints

• \(2 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)
• \(1 \leq c \leq 10^9\)

Example

3 4
1 2 3
2 3 1
1 3 7
2 1 5

2

Cho một ma trận lưới \(n * m\), các ô vuông được thể hiện bởi chữ số. Từ một ô vuông có thể đi sang \(4\) ô kề cạnh. Viết chương trình tìm đường đi từ \((x,y)\) đến \((u,v)\) có tổng các ô chữ số là nhỏ nhất.

• \((i, j)\) là ô hàng \(i\) cột \(j\).
• Ký tự \(G\) là ô \((x, y)\).
• Ký tự \(R\) là ô \((u, v)\).

Input

• Dòng đầu tiên: Hai số nguyên dương \(n\) và \(m\)
• \(n\) dòng tiếp theo: Mô tả ma trận lưới.
• Giới hạn: \(n, m \le 1000\)

Output

• Độ dài đường đi.

Sample Input

3 3
323
G9R
018

Sample Output

8

Nhiệm vụ của bạn là tìm \(k\) lộ trình bay ngắn nhất từ Syrjälä đến Metsälä. Một lộ trình có thể đi qua một thành phố vài lần.

Lưu ý rằng có thể có một số lộ trình với cùng một mức giá và mỗi lộ trình nên được xét (xem ví dụ).

Input

• Dòng đầu vào đầu tiên có ba số nguyên \(n\), \(m\), và \(k\): số lượng thành phố, chuyến bay, và tham số \(k\). Các thành phố được đánh số \(1, 2, \ldots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Metsälä.
• Sau này, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\), và \(c\): chuyến bay bắt đầu tại thành phố \(a\), kết thúc tại thành phố \(b\), và giá của nó là \(c\). Tất cả các chuyến bay đều là chuyến bay một chiều.
• Bạn có thể giả định rằng có ít nhất \(k\) lộ trình phân biệt từ Syrjälä đến Metsälä.

Constraints

• \(2 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)
• \(1 \leq c \leq 10^9\)
• \(1 \leq k \leq 10\)

Output

• In \(k\) số nguyên: giá của \(k\) tuyến đường rẻ nhất được sắp xếp theo giá của chúng.

Example

4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1

4 4 7

Bạn dự định đi từ Syrjälä đến Lehmälä bằng máy bay. Bạn muốn tìm câu trả lời cho các câu hỏi sau:

• giá rẻ nhất của một lộ trình như vậy là bao nhiêu?
• có bao nhiêu lộ trình với giá rẻ nhất? (chia lấy dư cho \(10^9 + 7\))
• số lượng chuyến bay tối thiểu của một lộ trình với giá rẻ nhất là bao nhiêu?
• số lượng chuyến bay tối đa của một lộ trình với giá rẻ nhất là bao nhiêu?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): số lượng thành phố và chuyến bay. Các thành phố được đánh số \(1, 2, \ldots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Lehmälä.
• Sau này, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên \(a\), \(b\), và \(c\): có một chuyến bay từ thành phố \(a\) đến thành phố \(b\) với giá \(c\). Tất cả chuyến bay đều là chuyến bay một chiều.
• Bạn có thể giả định rằng có một lộ trình từ Syrjälä đến Lehmälä.

Constraints

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)
• \(1 \leq c \leq 10^9\)

Example

4 5
1 4 5
1 2 4
2 4 5
1 3 2
3 4 3

5 2 1 2

Nguồn: Bài tập thầy Đỗ Đức Đông năm 2019