HBC24723焦虑的蚂蚁,排序,贪心[USACO 2010 Feb S]Chocolate Giving题解

凯凯我们等你回来算法基础篇 2023-11-20 13:05:02 47 0

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

Farmer John is distributing chocolates at the barn for Valentine's day, and B (1

Farmer John is distributing chocolates at the barn for Valentine's day, and B (1 <= B <= 25,000) of his bulls have a special cow in mind to receive a chocolate gift. Each of the bulls and cows is grazing alone in one of the farm's N (2*B <= N <= 50,000) pastures conveniently numbered 1..N and connected by M (N-1 <= M <= 100,000) bidirectional cowpaths of various lengths. Some pastures might be directly connected by more than one cowpath. Cowpath i connects pastures R_i R i and S_i S i (1 <= R_i R i <= N; 1 <= S_i S i <= N) and has length L_i L i (1 <= L_i L i <= 2,000). Bull i resides in pasture P_i P i (1 <= P_i P i <= N) and wishes to give a chocolate to the cow in pasture Q_i Q i (1 <= Q_i Q i <= N). Help the bulls find the shortest path from their current pasture to the barn (which is located at pasture 1) and then onward to the pasture where their special cow is grazing. The barn connects, one way or another (potentially via other cowpaths and pastures) to every pasture. As an example, consider a farm with 6 pastures, 6 paths, and 3 bulls (in pastures 2, 3, and 5) who wish to bestow chocolates on their love-objects: *1 <-- Bull wants chocolates for pasture 1 cow [4]--3--[5] <-- [5] is the pasture ID / | / | 4 2 <-- 2 is the cowpath length / | between [3] and [4] [1]--1--[3]*6 / / 9 3 2 / / [6] [2]*4 * The Bull in pasture 2 can travel distance 3 (two different ways) to get to the barn then travel distance 2+1 to pastures [3] and [4] to gift his chocolate. That's 6 altogether. * The Bull in pasture 5 can travel to pasture 4 (distance 3), then pastures 3 and 1 (total: 3 + 2 + 1 = 6) to bestow his chocolate offer. * The Bull in pasture 3 can travel distance 1 to pasture 1 and then take his chocolate 9 more to pasture 6, a total distance of 10.