邻接表，结构体存边(bellman-ford算法)

存边不需要考虑重边与自环

邻接矩阵

1. 初始化
for(int i = 1 ; i <= n ; i ++ )
    for(int j = 1 ; j <= n ; j ++ )
        if(i == j) g[i][j] = 0;
        else g[i][j] = inf;

2. 存边
for(int i = 1 ; i <= m ; i ++ )
{
    int a, b, c;
    cin >> a >> b >> c;

    g[a][b] = min(g[a][b], c); // 重边存最小的, 正权自环都大于0
}

原因主要在于松弛的三角不等式的不同

结构体，邻接表

dis[j] = min(dis[j], dis[t] + w[i]);

邻接数组

dis[j] = min(dis[j], dis[t] + g[t][j]);

对于重边而言, 输入时g[t][j]会被覆盖掉, 而w[i]是存在一个新开的空间中, 不会被覆盖, 使得更新时会长的边自然就会被更新掉, 所以存边时不需要管重边。

而对于自环而言, 邻接矩阵在取min时自环就会被淘汰掉, 邻接表与结构体在求最短路时, 如果存在自环正权不走, 最短路会更小, 负环没有最短路, 所以也不需要考虑。