7.18学习资料

组员:我、李青宸、徐铭泽、李秉恒、陈仲安
一、压位高精除
在一个元素中存储多个数值,减少时空复杂度
二、图论
1.最短路径
Dijkstra:单源
Floyd:多源、费时空复杂度
Spfa:它死了
2.存储

存图

邻接矩阵、邻接表(把一个点连着的边都用一个 vector 存起来,每个边具有一个指针,指向点连着的下一条边)。
3.查找

for(int i=head[u];i;i=e[i].next) int v=e[i].to;

4.例题
链式前向星:struct 存边,存储 to(边的端点),next(下一条边),val(边权)

飞行路线

核心代码:

if d[v][i] >= d[u][i] + w 			d[v][i] = d[u][i] + w;
if d[v][i] >= d[u][i - 1] 			d[v][i] = d[u][i - 1];

城市

核心代码:

if f[i][j] == f[i][k] + f[k][j] 	p[i][j] = 0;