Tap here to switch tabs
Problem
Submissions

Problem: Minimum Cost to Buy Apples

Try to solve the Minimum Cost to Buy Apples problem.

Statement

You are given an integer n representing nn cities numbered from 11 to n. You are also given a 22D integer array roads where roads[i] = [ai,bi,costi][a_i, b_i, cost_i] indicates that there is a bidirectional road connecting city aia_i and city bib_i with a travel cost of costicost_i.

Additionally, you are given an integer array appleCost of length n, where appleCost[i] is the cost of purchasing an apple in city i+1i + 1, and an integer k.

Starting from city ii, you can travel to any city jj (where jj can be equal to ii), buy an apple at city jj, and travel back to city ii. The total cost of this journey is:

  • The sum of the travel costs of the roads used to travel from city ii to city jj.

  • The cost of purchasing the apple at city jj, which is appleCost[j - 1].

  • The sum of the travel costs of the roads used to return from city jj to city ii, multiplied by k.

Return an integer array of size n where the ii-th value is the minimum total cost to start at city i+1i + 1, buy an apple, and return to city i+1i + 1.

Constraints:

  • 2≤2 \leq n ≤1000\leq 1000

  • 1≤1 \leq roads.length ≤2000\leq 2000

  • roads[i].length =3= 3

  • 1≤ai,bi≤1 \leq a_i, b_i \leq n

  • ai≠bia_i \neq b_i

  • 1≤costi≤1051 \leq cost_i \leq 10^5

  • appleCost.length ==== n

  • 1≤1 \leq appleCost[i] ≤105\leq 10^5

  • 1≤1 \leq k ≤100\leq 100

  • There are no repeated edges.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Cost to Buy Apples

Try to solve the Minimum Cost to Buy Apples problem.

Statement

You are given an integer n representing nn cities numbered from 11 to n. You are also given a 22D integer array roads where roads[i] = [ai,bi,costi][a_i, b_i, cost_i] indicates that there is a bidirectional road connecting city aia_i and city bib_i with a travel cost of costicost_i.

Additionally, you are given an integer array appleCost of length n, where appleCost[i] is the cost of purchasing an apple in city i+1i + 1, and an integer k.

Starting from city ii, you can travel to any city jj (where jj can be equal to ii), buy an apple at city jj, and travel back to city ii. The total cost of this journey is:

  • The sum of the travel costs of the roads used to travel from city ii to city jj.

  • The cost of purchasing the apple at city jj, which is appleCost[j - 1].

  • The sum of the travel costs of the roads used to return from city jj to city ii, multiplied by k.

Return an integer array of size n where the ii-th value is the minimum total cost to start at city i+1i + 1, buy an apple, and return to city i+1i + 1.

Constraints:

  • 2≤2 \leq n ≤1000\leq 1000

  • 1≤1 \leq roads.length ≤2000\leq 2000

  • roads[i].length =3= 3

  • 1≤ai,bi≤1 \leq a_i, b_i \leq n

  • ai≠bia_i \neq b_i

  • 1≤costi≤1051 \leq cost_i \leq 10^5

  • appleCost.length ==== n

  • 1≤1 \leq appleCost[i] ≤105\leq 10^5

  • 1≤1 \leq k ≤100\leq 100

  • There are no repeated edges.