组员:我、李青宸、徐铭泽、李秉恒、陈仲安
一、压位高精除
在一个元素中存储多个数值,减少时空复杂度
二、图论
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;