문제
Find the minimum total route cost from city 1 to each city. Routes are directed: [u, v, cost] allows travel from u to v, not automatically back. You may use several routes. City 1 costs 0 to reach. Every city is reachable from city 1.
Implement shortest_weighted_routes(cities, routes).
Input
cities: Number of cities, numbered from 1.
routes: Directed routes [from_city, to_city, cost].
Output
Return the minimum costs in city order, starting with city 1.
제약 조건
1 ≤ cities ≤ 100,000. 0…200,000 routes; endpoints are 1…cities. Costs are integers from 1 to 1,000,000,000. Parallel routes and self-loops are allowed. Distances fit signed 64-bit.
예시
입력:
cities = 3
routes = [
[1, 2, 5],
[1, 3, 1],
[3, 2, 2]
]
예상 출력:
expected = [0, 3, 1]입력:
long long cities = 3;
std::vector<std::vector<long long>> routes = {
{1, 2, 5},
{1, 3, 1},
{3, 2, 2}
};
예상 출력:
std::vector<long long> expected = {0, 3, 1};입력:
long cities = 3;
long[][] routes = new long[][] {
new long[] {1, 2, 5},
new long[] {1, 3, 1},
new long[] {3, 2, 2}
};
예상 출력:
long[] expected = new long[] {0, 3, 1};설명
City 3 costs 1. Going from 1 through 3 to 2 costs 1 + 2 = 3, cheaper than the direct cost of 5.
입력:
cities = 1
routes = []
예상 출력:
expected = [0]입력:
long long cities = 1;
std::vector<std::vector<long long>> routes = {};
예상 출력:
std::vector<long long> expected = {0};입력:
long cities = 1;
long[][] routes = new long[][] {};
예상 출력:
long[] expected = new long[] {0};설명
The only city is the starting city. No travel is needed, so its distance is 0.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
모든 경로 비용은 양수이므로, 아직 방문하지 않은 도시 중 가장 싼 곳부터 확장하세요.
힌트 2
방향성 인접 리스트를 만들고, 우선순위 큐로 나가는 경로를 계속 완화하세요.
힌트 3
평행 경로와 자기 루프가 있어도 괜찮고, 새로 찾은 경로가 더 싸면 그때만 갱신하세요.
예상 복잡도
시간 O((cities + routes) log cities), 추가 공간 O(cities + routes)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.