记录一些东西，当备忘录用

⭐1 spfa判断负环（正环）的时候，dist数组初始值是多少都行，但这个前提是你最初要把所有点都放进队列，因为这样才能确保有点能够更新其他点。如果是只加一个点（当然要确保这个点能走到环），dist数组还是要初始化成正无穷（最短路判负环）或者负无穷（最长路判正环）的。

⭐2 堆优化的迪杰斯特拉算法，每个点第一次出队的时候就是其最短路，第二次出队就是其第二短路，第k次出队就是其第k短路。

⭐3 一个广为人知的结论：图的染色问题中，最少颜色数量=最大团点的数量，但实际上这句话是错误的，因为只有 完美图才能满足这句话，而完美图的充要条件是：该图不包含点数大于等于5的奇数环（奇数环是指点数为奇数的环）。实际上这个充要条件目前也是个猜想，未被证明。

⭐4 在Bellman-Ford算法和Floyd算法中，有可能出现不可到达的两个点互相更新的情况，所以要判断一下dist[i][j]>=INF/2

⭐5 设a矩阵为恰好经过d1条边的最短路径矩阵，设b矩阵为恰好经过d1条边的最短路径矩阵，则通过一下这种加法后，c矩阵就是恰好经过(d1+d2)条边的最短路径矩阵

void add(int c[][N],int a[][N],int b[][N]) 
{
    static int temp[N][N];
    memset(temp,0x3f,sizeof temp);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                temp[i][j]=min(temp[i][j],a[i][k]+b[k][j]);
    memcpy(c,temp,sizeof temp);
}

具体题目 345.牛站