Nội dung Bài tập
- Mã:
- DHLTNC_DSU_10
- Tên:
- Đường đi trọng số nhỏ nhất
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4201103089
Cho đồ thị vô hướng n đỉnh , m cạnh . Trên mỗi đỉnh của đồ thị , có gắn một số tượng trưng cho giá trị của đỉnh đó . Trọng số của một đường đi chính bằng giá trị nhỏ nhất của các đỉnh thuộc đường đi đó . F(u , v) là giá trị lớn nhất trong của trọng số của các đường đi từ u -> v .
Yêu cầu : Tính tổng các F(u , v) với (u # v) .
INPUT :
Dòng đầu tiên gồm 2 số nguyên dương n , m ( n < 105 , m < 2.105 ) .
Dòng thứ 2 gồm n số là giá trị các đỉnh : a1 , a2 , .. , an . ( 0 < ai < 109 ).
m dòng tiếp theo là các cạnh đồ thị . Mỗi dòng gồm 2 số nguyên dương u , v ( 1 < u , v < n ).
OUTPUT :
Kết quả bài toán .
VÍ DỤ
- Input4 3
10 20 30 40
1 3
2 3
4 3Output200
- Giải thích:
- u = 1 , v = 3 , F(u , v) = 10.
- u = 2 , v = 3 , F(u , v) = 20.
- u = 4 , v = 3 , F(u , v) = 30.
- u = 1 , v = 2 , F(u , v) = 10.
- u = 2 , v = 4 , F(u , v) = 20.
- u = 4 , v = 1 , F(u , v) = 10.
Tổng là 100 x 2 = 200 .
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <bits/stdc++.h>using namespace std;//Tự cho là gồm 4 chữ số , vì đề bài k n...