HBC24625younik要排号,数据结构,STL,模拟[USACO 2011 Mar S]Package Delivery题解

想要成为编程高手？那就来试试全网最全C++题库，让您在练习中快速成长。

Farmer John must deliver a package to Farmer Dan, and is preparing to make his journey. To keep the peace, he gives a tasty treat to every cow that he meets along his way and, of course, FJ is so frugal that he would like to encounter as few cows as possible.

Farmer John must deliver a package to Farmer Dan, and is preparing to make his journey. To keep the peace, he gives a tasty treat to every cow that he meets along his way and, of course, FJ is so frugal that he would like to encounter as few cows as possible. FJ has plotted a map of N (1 <= N <= 50,000) barns, connected by M (1 <= M <= 50,000) bi-directional cow paths, each with C_i C i ​ (0 <= C_i C i ​ <= 1,000) cows ambling along it. A cow path connects two distinct barns, A_i A i ​ and B_i B i ​ (1 <= A_i A i ​ <= N; 1 <= B_i B i ​ <= N; A_i A i ​ != B_i B i ​ ). Two barns may be directly connected by more than one path. He is currently located at barn 1, and Farmer Dan is located at barn N. Consider the following map: [2]--- / | /1 | 6 / | [1] 0| --[3] | / 2 4 | /4 [6] | / /1 [4]-----[5] 3 The best path for Farmer John to take is to go from 1 -> 2 -> 4 -> 5 -> 6, because it will cost him 1 + 0 + 3 + 1 = 5 treats. Given FJ's map, what is the minimal number of treats that he should bring with him, given that he will feed each distinct cow he meets exactly one treat? He does not care about the length of his journey.

成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。

标签： HBC24625younik要排号 数据结构 STL 模拟[USACO 2011 Mar S]Package Delivery题解