Pergunta

IMG_2870.jpeg
IMG_2869.jpeg
IMG_2868.jpeg
IMG_2867.jpeg
IMG_2866.jpeg
IMG_2865.jpeg

Solve this 8/15 test cases passed

Pensamento

Clarifying transition costs for path calculations

The total cost between hubs seems to depend on the transition time leaving each hub, not the direction. For example, traveling from Hub 1 to Hub 3 (counterclockwise) costs transition[1], while the direct route from Hub 1 to Hub 2 costs transition[1] as well. After careful analysis, the graph appears directed, and path costs are confirmed.

Thought for 36s

Resposta

Your failing cases are because ccw = total - cw is not valid here.

hubTransitionTimes[i] is the cost to leave hub i, no matter which adjacent hub you go to. So clockwise and counterclockwise routes do not complement each other like normal undirected edge weights.

Use this instead:

cpp
long computeMinDeliveryTime(vector<int> deliverySequence, vector<int> hubTransitionTimes) { int m = hubTransitionTimes.size(); // pref[i] = sum of hubTransitionTimes[1..i], 1-based logically vector<long long> pref(m + 1, 0); for (int i = 1; i <= m; i++) { pref[i] = pref[i - 1] + hubTransitionTimes[i - 1]; } auto clockwise = [&](int from, int to) -> long long { if (from == to) return 0; if (from < to) { // from -> from+1 -> ... -> to return pref[to - 1] - pref[from - 1]; } else { // from -> ... -> m -> 1 -> ... -> to return (pref[m] - pref[from - 1]) + pref[to - 1]; } }; auto counterClockwise = [&](int from, int to) -> long long { if (from == to) return 0; if (from > to) { // from -> from-1 -> ... -> to return pref[from] - pref[to]; } else { // from -> ... -> 1 -> m -> ... -> to return pref[from] + (pref[m] - pref[to]); } }; long long ans = 0; int cur = 1; for (int dest : deliverySequence) { long long cw = clockwise(cur, dest); long long ccw = counterClockwise(cur, dest); ans += min(cw, ccw); cur = dest; } return ans; }

Also, your prefix loop has an out-of-bounds bug:

cpp
for(int i = 0; i <= m; i++) prefix[i+1] = prefix[i] + hubTransitionTimes[i-1];

At i = 0, it reads hubTransitionTimes[-1]. At i = m, it reads hubTransitionTimes[m]. Both are invalid.

The corrected prefix loop is:

cpp
for (int i = 1; i <= m; i++) { pref[i] = pref[i - 1] + hubTransitionTimes[i - 1]; }

Compartilhar esta Q&A