不带负权的最短路计数问题 -> 直接用dijkstra, bfs写, 不能用spfa写
注意：我说的是不能在算法中同时维护出最短路的条数，因为spfa算法出队顺序不满足拓扑序，不能递推得到。
直接用bfs或dijkstra跑一遍并顺带统计cnt即可(因为其出队顺序就是拓扑序), 但spfa不行, 因为其不自带拓扑序

// 统计cnt代码 c为常数
int count = cnt[id][type];

1. if(dis[j][c] == dis[ver][c] + w[i]) cnt[j] += count;
2. if(dis[j][c] > dis[ver][c] + w[i]) 
{
    1) c == 0 -> cnt[j][1] = cnt[j][0], cnt[j][0] = count;
    2) c == 1 -> cnt[j][1] = count;
}

例题 最短路计数
例题 观光

带负权的最短路计数问题
先跑一遍spfa, 再排拓扑序, 再统计
(目前不会, 待更新…)

如果要有正权环的话, 那么最短路一定不会走过这个环.
如果要有负权环的话, 这个最短路一定不存在.

我们就可以知道, 如果最短路走过了环, 该环一定是边权为0的环, 那么最短路的数量将为无限条, 所以既然叫我们求最短路的条数那么一定不含非正环. 但是最短路不会走过正权环, 所以直接忽略. 即拓扑序.