| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P174PROG - ROUND 4G - Truy vấn trên đồ thị |
Đồ thị G gồm các đỉnh được đánh số bằng các số nguyên dương từ 1. Mỗi đỉnh thứ i của đồ có cạnh nối 2 chiều đến các đỉnh i + i và i + i + 1. Ta định nghĩa đường đi ngắn nhất từ u đến v là đường đi từ u đến v và có tổng số lượng các cạnh ít nhất. Ban đầu trọng số của tất cả các cạnh đều bằng 0. Có 2 loại truy vấn:
- Truy vấn 1: Tăng trọng số tất cả các cạnh thuộc đường đi ngắn nhất từ đỉnh u tới đỉnh v một giá trị w.
- Truy vấn 2: Tìm tổng trọng số của đường đi ngắn nhất từ đỉnh u đến đỉnh v.
Input
Dòng đầu tiên gồm 1 số nguyên dương q (0 < q < 1 001) – số lượng truy vấn.
q dòng tiếp theo gồm các truy vấn, truy vấn loại 1 có dạng: 1 u v w (0 < u < v < 10 ^ 18 + 1, 0 < w < 10 ^ 9) có nghĩa trọng số mỗi cạnh thuộc đường đi ngắn nhất từ u đến v tăng lên 1 lượng giá trị w, truy vấn loại 2 có dạng 2 u v (0 < u < v < 10 ^ 18 + 1) có nghĩa cần đưa ra giá trị tổng trọng số của đường đi ngắn nhất từ u tới v. Các số u, v, w đếu là số nguyên.
Output
Với mỗi truy vấn loại 2, in ra đáp án của truy vấn, mỗi đáp án in trên 1 dòng.
Example
Input:
8
1 11 4 7
2 9 12
2 7 1
2 3 11
2 7 9
1 12 5 7
1 8 6 7
2 11 2
Output:
7
0
14
7
21
| Được gửi lên bởi: | adm |
| Ngày: | 2017-03-10 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
