#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Problem statement

There is a kind of problems which want you to calculate the distant of the shortest path from some verdicts to other verdicts. This kind of problems are called "shortest path" in graph.

For example, in this graph, the distant of shortest path from verdict $$$1$$$ to verdict $$$6$$$ is $$$6$$$. And the distant of the shortest path from verdict $$$1$$$ to verdict $$$4$$$ is $$$5$$$.

Specifically, there are $$$2$$$ of subproblems in shortest path:

Single sourse (one start point)
Multi source (multi start point)

Dijkstra and shortest path with single sourse

In shortest path with single sourse, we should calculate the distant of the shortest path from one verdict (Lets suppose the sourse is verduct $$$1$$$) to others. Dijkstra is the most common algorithm to solve this sort of problems.

Node that Dijkstra can only solve the problems with nonnegtive edge weight. For graphs with negtive edge weight, you can only use Bellman Ford.

Dijkstra is a kind of greedy. In each turn, We select the verdict with the shortest distance from the sourse and get the shortest path to it. After that we update the distant from the sourse to other verdict.