trang chủ / đề bài / icpcwf13_c

Chắc chắn bạn sẽ gây tắc đường

Đề bài

Mô tả

Bạn phụ trách thiết kế một hệ thống điều phối giao thông tập trung tiên tiến dành cho ô tô thông minh. Mục tiêu là dùng thông tin toàn cục để hướng dẫn những người đi làm buổi sáng, những người phải lái xe từ ngoại ô vào trung tâm thành phố, đi đến trung tâm theo cách tốt nhất mà không bị tắc đường.

Đáng tiếc là những người đi làm đều thuộc đường và ích kỷ, nên bạn không thể bảo họ đi theo một tuyến mất nhiều thời gian hơn bình thường (nếu vậy họ sẽ phớt lờ chỉ dẫn của bạn). Bạn chỉ có thể thuyết phục họ đổi sang một tuyến khác nhanh bằng đúng như vậy.

Mạng lưới đường của thành phố gồm các giao lộ được nối với nhau bởi các con đường hai chiều với thời gian di chuyển khác nhau. Mỗi người bắt đầu ở một giao lộ nào đó (giao lộ xuất phát có thể khác nhau giữa những người). Tất cả đều kết thúc hành trình ở cùng một nơi: trung tâm thành phố, tức giao lộ 1. Nếu hai người cùng bắt đầu đi vào một con đường theo cùng một chiều tại cùng một thời điểm thì sẽ xảy ra tắc đường; bạn phải tránh điều này. Tuy nhiên, hai người được phép đi qua cùng một giao lộ cùng lúc, và được phép đi vào cùng một con đường tại hai thời điểm khác nhau.

Hãy xác định số lượng lớn nhất người đi làm có thể lái xe vào trung tâm mà không gây tắc đường, với điều kiện tất cả bắt đầu hành trình tại đúng cùng một thời điểm và không ai đi theo một tuyến không tối ưu (mỗi người được chọn đều phải đi theo một đường đi ngắn nhất từ giao lộ xuất phát của mình tới giao lộ 1).

Hình dưới minh họa ví dụ thứ hai: số trên mỗi cạnh là thời gian đi qua con đường đó, nhãn cạnh mỗi đỉnh là số xe xuất phát ở đó.

graph weighted
4 4
1 2 5
1 3 4
4 2 5
4 3 6
label 1 1 xe
label 4 4 xe
path orange 4 3 1
path green 4 2 1

Một xe đã ở sẵn trung tâm. Trong bốn xe ở giao lộ 4, một xe có thể đi theo tuyến màu cam qua giao lộ 3, một xe khác đi theo tuyến màu xanh lá qua giao lộ 2 (cả hai tuyến đều dài 10). Hai xe còn lại không thể vào trung tâm mà không gây tắc đường. Vậy tối đa 3 xe vào được trung tâm mà không tắc đường.

Dữ liệu vào

Dữ liệu gồm một test duy nhất. Dòng đầu tiên chứa ba số nguyên n, m và c: n là số giao lộ, m là số con đường và c là số người đi làm. Mỗi dòng trong m dòng tiếp theo chứa ba số nguyên xi, yi và ti mô tả một con đường: xi và yi là hai giao lộ phân biệt mà con đường nối, ti là thời gian đi hết con đường theo chiều nào cũng vậy. Dòng cuối cùng chứa c số nguyên là các giao lộ xuất phát của những người đi làm.

Dữ liệu ra

In ra số lượng lớn nhất người đi làm có thể vào trung tâm mà không gây tắc đường.

Ràng buộc

  • 1≤n≤25000, 0≤m≤50000, 0≤c≤1000.
  • 1≤xi,yi≤n, xi≠yi, 1≤ti≤10000. Giữa hai giao lộ có thể có nhiều con đường.
  • Từ mọi giao lộ đều có thể đi tới trung tâm (giao lộ 1).
  • Các giao lộ xuất phát nằm trong khoảng [1,n]; nhiều người có thể xuất phát ở cùng một giao lộ, kể cả giao lộ 1.

Ví dụ

Input Output Giải thích
3 3 2
1 2 42
2 3 1
2 3 1
2 3
2 Người ở giao lộ 2 đi thẳng con đường 2→1 từ thời điểm 0. Người ở giao lộ 3 đi một trong hai con đường 3→2, rồi vào con đường 2→1 ở thời điểm 1, khác thời điểm của người kia nên không tắc.
4 4 5
1 2 5
1 3 4
4 2 5
4 3 6
4 4 4 4 1
3 Ví dụ trong hình: người ở giao lộ 1 đã tới nơi, hai trong bốn người ở giao lộ 4 đi theo hai tuyến 4→3→1 và 4→2→1.

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