请编写程序求给定正权有向图的单源最短路径长度。图中包含n个顶点，编号为0至n-1，以顶点0作为源点。

输入格式:

输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过1000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。

输出格式:

输出为一行整数，为按顶点编号顺序排列的源点0到各顶点的最短路径长度（不含源点到源点），每个整数后一个空格。如源点到某顶点无最短路径，则不输出该条路径长度。

输入样例:

1
2
3
4
5
4 4
0 1 1
0 3 1
1 3 1
2 0 1

输出样例:

1
1 1

思路：

  • 这里采取的是邻接表存储信息的操作，因为n值较大，设置dis数组存储源点到各个点的最短距离，注意初始化
  • 采用了最普通的Dijkstra算法，每次寻找最小权值，并判断是否可以进行松弛。
  • 最后输出时注意，无最短路径时（即两点间距离为无穷时），不输出对应的dis值

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
using namespace std;

typedef struct {
    int v, w;
} Node;

const int inf = 65535;
int n, e;
int dis[20001];
vector<Node> v[20001];
bool vis[20001] = {false};

void dijkstra(int s) {
    fill(dis, dis + 20001, inf);
    dis[0] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, minx = inf;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && dis[j] < minx) {
                u = j;
                minx = dis[j];
            }
        }
        if (u == -1)
            break;
        vis[u] = true;
        for (int j = 0; j < v[u].size(); j++) {
            int x = v[u][j].v;
            if (!vis[x] && dis[u] + v[u][j].w < dis[x]) {
                dis[x] = dis[u] + v[u][j].w;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &e);
    for (int i = 0; i < e; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back(Node{b, c});
    }
    dijkstra(0);
    for (int i = 1; i < n; i++) {
        if (dis[i] != inf)
            printf("%d ", dis[i]);
    }
    return 0;
}