← 返回 snapchat 的题目列表Dijkstra-based Problem
类型：online_judge
Write a program to implement Dijkstra's algorithm. Given a weighted directed graph and a starting node, compute the shortest path distances from the starting node to all other nodes and return them as an array, where the i-th element represents the shortest distance from the starting node to node i. If a node is unreachable, return -1. The number of nodes will not exceed 1000, and the number of paths will not exceed 5000.
Input Format:
First, the number of nodes n and the number of edges m. Then follows m lines, each containing two integers u, v and an integer w, indicating that there is an edge from node u to node v with weight w. Finally, an integer start, indicating the starting node.
Output Format:
Output an array of length n, representing the shortest path lengths from the starting node to each node.
Sample Input:
4 4
0 1 1
1 2 2
0 2 4
2 3 1
0
Sample Output:
0 1 3 4
Example
Input
5 6
0 1 10
0 2 3
1 2 1
2 1 4
1 3 2
2 3 8
0