最短路 学习笔记

技巧性

二分最短路 [GDOI2018Day2T1]
最短路+枚举边/路径/点：[CF 544D]，[CF 954D]，最小环问题，[Bzoj 1880]
拆点最短路 [AHSOFNU-NOIP模拟-2-t3]

分层图最短路

[GDOI2016Day2T1]。

一般用来决策。

最短路图

最短路树 [CF1005F]。

涉及多条最短路时。

DP

DAG 图

拓扑序

(任意图DP) 无后效性量

[Luogu 1144], [NOIP2017Day1T3]， [Bzoj 1706]

SPFA / Dij 松弛带环DP

在不能贪心的时候不能用Dij，例如 Bzoj 3875，Luogu1875 ，这类题DP方程不同

可以贪心的：CF 938D

0-1 BFS

解边权为 0，1 的图最短路
用双端队列 deque 如果当前边权是 1 就放到队尾否则放到队首松弛最短路。
不要开vis数组！用dis松弛即可。

例题：CF 821D. CF 1072D, Loj 2632

堆优化dijkstra

#include<cstdio>  
#include<algorithm>  
#include<cstring>  
#include<queue>  
#define ms(i,j) memset(i,j, sizeof i);  
using namespace std;   
struct node//dijkstra结点   
{  
    int d;  
    int u;  
    bool operator<(const node &a) const//重载小于号，用于priority的比较   
    {  
        return d>a.d;  
    }  
};  
priority_queue<node> q; //堆  
int dis[2505];  
int vi[2505];   
int t,c,ts,te;   
int G[2505][2505];//邻接矩阵储存  
int dij()  
{  
    q.push((node){dis[ts], ts});//入堆   
    while (!q.empty())  
    {  
        node p = q.top(); q.pop();  
        if(vi[p.u]) continue;//已经标记过   
        vi[p.u] = true;  
        for (int i=1;i<=t;i++)//松弛   
        if(dis[p.u]+G[p.u][i]<dis[i])  
        {  
            dis[i] = dis[p.u]+G[p.u][i];  
            q.push((node){dis[i], i});  
        }  
    }  
}  
int main()  
{  
    scanf("%d%d%d%d", &t,&c,&ts,&te);  
    ms(G,127);//初始化矩阵   
    ms(vi,false);  
    ms(dis,127); dis[ts] = 0;  
    for (int i=1;i<=c;i++)  
    {  
        int rs,re,ci;  
        scanf("%d%d%d", &rs, &re, &ci);  
        G[rs][re] = G[re][rs] = ci;  
    }  
    dij();  
    printf("%d\n", dis[te]);  
    return 0;  
}