最短路 学习笔记

NEW

见做题针对题目,本页面基本上作废 qwq

0-1 BFS

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

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

堆优化dijkstra

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
52
#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;
}

OLD

模板及讲解

常见题型:
1、常规最短路
Q:求两点最短路。
解:堆优化dijkstra
例题:Tyvj 1031
2、次短路
Q:求两点次短路。
解:
例题:
3、最小环
Q:求两点最小环。
解:Floyd求最短路时顺便求出。
例题:vijos 1046
4、分层图最短路
Q:求两点最短路,其中可以免费走过k条边。
解:分层图最短路。
例题:BZOJ 2763
5、二分后最短路判定
Q:询问1到n路径上最大值,可以免费走过k条边。
解:二分后最短路判定。
例题:BZOJ1614
6、拆点
Q:一个点有两种属性。
解:把点拆成两个点$i, i+n$。
例题:AHSOFNU NOIP模拟题-2 T3
7、SPFA判负环
Q:给出一个带负边权的图,请判断该图是否有负环回路。
解:用SPFA,一个点进队超过$n$次就存在负环(BFS), 更新存在回路(DFS)。
例题:BZOJ 1715(BFS), Bzoj 1690(DFS)

------ 本文结束 ------