trang chủ / đề bài / greggraph

Xoá đỉnh và tổng khoảng cách

Đề bài

Mô tả

Cho một đồ thị có hướng, có trọng số gồm n đỉnh, trong đó giữa mỗi cặp đỉnh phân biệt đều có cạnh theo cả hai chiều. Cạnh đi từ đỉnh i tới đỉnh j có độ dài aij.

Người ta lần lượt xoá n đỉnh khỏi đồ thị: ở bước thứ i, đỉnh xi bị xoá cùng với mọi cạnh đi vào và đi ra khỏi nó.

Trước mỗi bước xoá, hãy tính tổng độ dài đường đi ngắn nhất giữa mọi cặp có thứ tự (u,v) gồm hai đỉnh phân biệt còn lại trong đồ thị. Đường đi ngắn nhất được phép đi qua bất kỳ đỉnh nào còn lại (và chỉ những đỉnh còn lại).

Dữ liệu vào

  • Dòng đầu chứa số nguyên n.
  • n dòng tiếp theo, dòng thứ i chứa n số nguyên ai1,ai2,…,ain là ma trận kề của đồ thị.
  • Dòng cuối chứa n số nguyên phân biệt x1,x2,…,xn là thứ tự các đỉnh bị xoá.

Dữ liệu ra

In ra n số nguyên trên một dòng, số thứ i là tổng cần tìm ngay trước bước xoá thứ i.

Ràng buộc

  • 1≤n≤500
  • 1≤aij≤105 với i≠j, aii=0
  • 1≤xi≤n, các xi đôi một phân biệt

Ví dụ

Input Output Giải thích
2
0 5
4 0
1 2
9 0 Trước bước 1, tổng là 5+4=9. Trước bước 2 chỉ còn đỉnh 2, tổng bằng 0.
4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3
17 23 404 0 Sau khi xoá đỉnh 4, còn các đỉnh 1, 2, 3 với tổng 23. Sau khi xoá thêm đỉnh 1, chỉ còn cạnh 2→3 dài 400 và 3→2 dài 4, tổng 404.
1
0
1
0 Chỉ có một đỉnh.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0