Single Source Shortest Path II
For a given weighted graph G=(V,E), find the shortest path from a source to each vertex. For each vertex u, print the total weight of edges on the shortest path from vertex 0 to u.
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $1$ | 正确数量 | $1$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | STL |
Single Source Shortest Path II
For a given weighted graph G=(V,E), find the shortest path from a source to each vertex. For each vertex u, print the total weight of edges on the shortest path from vertex 0 to u.
In the first line, an integer n denoting the number of vertices in G is given. In the following n lines, adjacency lists for each vertex u are respectively given in the following format:
u k v1 c1 v2 c2 ... vk ck
Vertices in G are named with IDs 0,1,...,n−1. u is ID of the target vertex and k denotes its degree. vi(i=1,2,...k)denote IDs of vertices adjacent to u and ci denotes the weight of a directed edge connecting u and vi (from u to vi).
5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3
0 0
1 2
2 2
3 1
4 3
1≤ n≤ 10,000
0≤ ci≤ 100,000
|E|< 500,000
All vertices are reachable from vertex 0
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$77 $ms] | 海燕 | 938913 | 2023-01-02 00:34:26 |
| 内存最少[$7472 $KB] | 海燕 | 938913 | 2023-01-02 00:34:26 |
| 第一AC | 海燕 | 938913 | 2023-01-02 00:34:26 |
| 第一挑战 | 海燕 | 938913 | 2023-01-02 00:34:26 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|