SMINROAD - Đường đi trọng số nhỏ nhất
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: namnguyen123

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ụ

  • input
    4 3
    10 20 30 40
    1 3
    2 3
    4 3
    output
    200
  • 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 . 

Back to Top