City and Concert
There are N cities numbered 1 to N connected by M bi-directional roads. A concert is going to be organized in each city and in city ith city it costs A[i] amount.
Every time you travel the ithroad connecting B[i][0] and B[1] city. It will cost B[i][2] amount
For each city i: 1 to N, find the minimum amount a person from city i has to pay to visit a concert in any of the city and come back to his own city.
It may not be guaranteed that each city is reachable from other city.
Problem Constraints
1<= N <= 10^5
0 <= M <= 2 * 10^5
1 <= A[i], B[i][2] <= 10^9
1 <=B[i][0] , B[i][1] <=N
Example Input
Input 1:
A [10, 2, 4, 15, 30]
B [
[1, 2, 3]
[3, 4, 5]
[4, 5, 4]
]
Input 2:
A - [4, 1, 1e, 15]
B = [
[2, 3, 2]
[3, 4, 2]
[1, 3, 3]
]
Example Output
Output 1:
[8, 2, 4, 14, 22]
Output 2:
[4, 1, 5, 9]
Example Explanation
Output 2
[4, 1, 5, 9)
Example Explanation
Explanation 1:
city 1: Person can travel to city 2 and attend concert then comeback to its own city. Total Amount (3 + 2 + 3) = 8.
city 2: Person can attend a concert in his own city at cost of 2.
City 3: Person can attend a concert in his own city at cost of 4.
City 4: Person can travel to city 3 and attend concert then comeback to its own city. Total Amount (5 + 4 + 5) = 14.
city 5: Person can travel to city 3 and attend concert then comeback to its own city. Total Amount (4+ 5+ 4 +5+ 4) = 22.
Explanation 2:
City 1: Person can attend a concert in his own duty at cost of 4.
City 2: Person can attend a concert in his own dty at cost of 1.
City 3: Person can travel to city 1 and attend concert then comeback to 1ts own city. Total Amount (2 + 1+ 2) = 5.
City 4: Person can travel to city 2 and attend concert then comeback to its own city. Total Amount (2+2+1+2+2) = 9.
Answers
Answer:
City and Concert
There are N cities numbered 1 to N connected by M bi-directional roads. A concert is going to be organized in each city and in city ith city it costs A[i] amount.
Every time you travel the ithroad connecting B[i][0] and B[1] city. It will cost B[i][2] amount
For each city i: 1 to N, find the minimum amount a person from city i has to pay to visit a concert in any of the city and come back to his own city.
It may not be guaranteed that each city is reachable from other city.
Problem Constraints
1<= N <= 10^5
0 <= M <= 2 * 10^5
1 <= A[i], B[i][2] <= 10^9
1 <=B[i][0] , B[i][1] <=N
Example Input
Input 1:
A [10, 2, 4, 15, 30]
Explanation:
There are N cities numbered 1 to N connected by M bi-directional roads. A concert is going to be organized in each city and in city ith city it costs A[i] amount.
Every time you travel the ithroad connecting B[i][0] and B[1] city. It will cost B[i][2] amount
For each city i: 1 to N, find the minimum amount a person from city i has to pay to visit a concert in any of the city and come back to his own city.
It may not be guaranteed that each city is reachable from other city.
Problem Constraints
1<= N <= 10^5
0 <= M <= 2 * 10^5
1 <= A[i], B[i][2] <= 10^9
1 <=B[i][0] , B[i][1] <=N
Example Input
Input 1:
A [10, 2, 4, 15, 30]
B [
[1, 2, 3]
[3, 4, 5]
[4, 5, 4]
]
Input 2:
A - [4, 1, 1e, 15]
B = [
[2, 3, 2]
[3, 4, 2]
[1, 3, 3]
]
Example Output
Output 1:
[8, 2, 4, 14, 22]
Output 2:
[4, 1, 5, 9]
Answer:
2, 3]
[3, 4, 5]
[4, 5, 4]
]
Input 2:
A - [4, 1, 1e, 15]
B = [
[2, 3, 2]
[3, 4, 2]
[1, 3, 3]
]
Example Output
Output 1:
[8, 2, 4, 14, 22]
Output 2:
[4, 1, 5, 9]
Example Explanation
Output 2