最短路径wt
1.弗洛伊德（Floyd ）
用来求解赋权图中每对顶点间的最短距离，Floyd算法是经典的动态规划算法，基本思想是递推产生一个矩阵序列A1,A2,…,Ak,…,An（图有n个节点），Ak=(ak(i,j))nxn。其中矩阵Ak第i行第j列表示从顶点vi到顶点vj的路径上经过的顶点序号不大于k的最短路径长度。
电车
题目描述
在一个神奇的小镇上有着一个特别的电车网络，它由一些路口和轨道组成，每个路口都连接着若干个轨道，每个轨道都通向一个路口（不排除有的观光轨道转一圈后返回路口的可能）。在每个路口，都有一个开关决定着出去的轨道，每个开关都有一个默认的状态，每辆电车行驶到路口之后，只能从开关所指向的轨道出去，如果电车司机想走另一个轨道，他就必须下车切换开关的状态。
为了行驶向目标地点，电车司机不得不经常下车来切换开关，于是，他们想请你写一个程序，计算一辆从路口 A A A 到路口 B B B 最少需要下车切换几次开关。
输入格式
第一行有 3 3 3 个整数 N , A , B N,A,B N,A,B（ 2 ≤ N ≤ 100 , 1 ≤ A , B ≤ N 2 \leq N \leq 100, 1 \leq A,B \leq N 2≤N≤100,1≤A,B≤N），分别表示路口的数量，和电车的起点，终点。
接下来有 N N N 行，每行的开头有一个数字 K i K_i Ki（ 0 ≤ K i ≤ N − 1 0 \leq K_i \leq N-1 0≤Ki≤N−1），表示这个路口与 K i K_i Ki 条轨道相连，接下来有 K i K_i Ki 个数字表示每条轨道所通向的路口，开关默认指向第一个数字表示的轨道。
输出格式
输出文件只有一个数字，表示从 A A A 到 B B B 所需的最少的切换开关次数，若无法从 A A A 前往 B B B，输出 − 1 -1 −1。
样例 #1
样例输入 #1
3 2 1
2 2 3
2 3 1
2 1 2
1
2
3
4
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n, s, e, m, x, f[1001][1001];
void floy()
{
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (!(i == j || i == k || j == k))
{
f[i][j] = min(f[i][k] + f[k][j], f[i][j]);
}
}
}
}
}
int main()
{
memset(f, INF, sizeof(f));
cin>>n>>s>>e;
for (int i = 1; i <= n; i++)
{
f[i][i] = 0;
}
for (int i = 1; i <= n; i++)
{
cin >> m;
for (int j = 1; j <= m; j++)
{
cin >> x;
if (j == 1)
{
f[i][x] = 0;
}
else
{
f[i][x] = 1;
}
}
}
floy();
if (f[s][e] == INF)
{
cout << "-1";
}
else
{
cout<<f[s][e];
}
return 0;
}样例输出 #1
0
1
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
53
54
55
通过中间点k求得是从i —> j近还是从i —> k —> j 近，从而求得点a到点b的最短路径（a和b都是随机点）可以把一个路口看作一张图中的一个点，轨道是图中的边（注意：这是有向图），每一条边的权值就是这个边所联通的点是否需要按按钮（需要按按钮就是1，不需要按按钮就是0）然后就用求最短路径的算法算出最少需要按的开关数。
2.迪杰斯特拉（dijkstra）
在已知图的邻接矩阵的条件下，通过遍历已知图的所有路径，用 dis[i] 数组来记录到i点的最短路径，然后在循环中不断判断更替。首先，将所有点的集合分为俩部分，一边是已经遍历过的，另外一边是没有遍历过的，分别用mark[i]=1、mark[i]=0来表示。层层扩散，实时比较和更新最短路径。
以起始点为中心向外层层扩展，直到扩展到终点为止。由for循环可知，其时间复杂度是O（n^2）。
【模板】单源最短路径（弱化版）
题目背景
本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 n , m , s n,m,s n,m,s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 m m m 行每行包含三个整数 u , v , w u,v,w u,v,w，表示一条 u → v u \to v u→v 的，长度为 w w w 的边。
输出格式
输出一行 n n n 个整数，第 i i i 个表示 s s s 到第 i i i 个点的最短路径，若不能到达则输出 2 31 − 1 2^{31}-1 231−1。
样例 #1
样例输入 #1
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
1
2
3
4
5
6
7
样例输出 #1
0 2 4 3
1
提示
【数据范围】
对于 20 % 20\% 20% 的数据： 1 ≤ n ≤ 5 1\le n \le 5 1≤n≤5， 1 ≤ m ≤ 15 1\le m \le 15 1≤m≤15；
对于 40 % 40\% 40% 的数据： 1 ≤ n ≤ 100 1\le n \le 100 1≤n≤100， 1 ≤ m ≤ 1 0 4 1\le m \le 10^4 1≤m≤104；
对于 70 % 70\% 70% 的数据： 1 ≤ n ≤ 1000 1\le n \le 1000 1≤n≤1000， 1 ≤ m ≤ 1 0 5 1\le m \le 10^5 1≤m≤105；
对于 100 % 100\% 100% 的数据： 1 ≤ n ≤ 1 0 4 1 \le n \le 10^4 1≤n≤104， 1 ≤ m ≤ 5 × 1 0 5 1\le m \le 5\times 10^5 1≤m≤5×105， 1 ≤ u , v ≤ n 1\le u,v\le n 1≤u,v≤n， w ≥ 0 w\ge 0 w≥0， ∑ w < 2 31 \sum w< 2^{31} ∑w<231，保证数据随机。
Update 2022/07/29：两个点之间可能有多条边，敬请注意。
对于真正 100 % 100\% 100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。
样例说明：
图片1到3和1到4的文字位置调换
#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
#define maxm 500005
#define INF 1234567890
inline int read()
{
int x=0,k=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
struct Edge
{
int u,v,w,next;
}e[maxm];
int head[maxn],cnt,n,m,s,vis[maxn],dis[maxn];
struct node
{
int w,now;
inline bool operator <(const node &x)const
//重载运算符把最小的元素放在堆顶（大根堆）
{
return w>x.w;//这里注意符号要为'>'
}
};
priority_queue<node>q;
//优先队列，其实这里一般使用一个pair，但为了方便理解所以用的结构体
inline void add(int u,int v,int w)
{
e[++cnt].u=u;
//这句话对于此题不需要，但在缩点之类的问题还是有用的
e[cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
//存储该点的下一条边
head[u]=cnt;
//更新目前该点的最后一条边（就是这一条边）
}
//链式前向星加边
void dijkstra()
{
for(int i=1;i<=n;i++)
{
dis[i]=INF;
}
dis[s]=0;
//赋初值
q.push((node){0,s});
while(!q.empty())
//堆为空即为所有点都更新
{
node x=q.top();
q.pop();
int u=x.now;
//记录堆顶（堆内最小的边）并将其弹出
if(vis[u]) continue;
//没有遍历过才需要遍历
vis[u]=1;
for(int i=head[u];i;i=e[i].next)
//搜索堆顶所有连边
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
//松弛操作
q.push((node){dis[v],v});
//把新遍历到的点加入堆中
}
}
}
}
int main()
{
n=read(),m=read(),s=read();
for(int i=1,x,y,z;i<=m;i++)
{
x=read(),y=read(),z=read();
add(x,y,z);
}
dijkstra();
for(int i=1;i<=n;i++)
{
printf("%d ",dis[i]);
}
return 0;
}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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
首先用数组dis记录起点到每个结点的最短路径，再用一个数组保存已经找到最短路径的点
然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点记为已经找到最短路
此时完成一个顶点，再看这个点能否到达其它点（记为v），将dis[v]的值进行更新
不断重复上述动作，将所有的点都更新到最短路径
迪杰斯特拉算法：
迪杰斯特拉算法是一种用于求解最短路径的算法，它可以在一个有向图中求出从一个顶点到其他所有顶点的最短路径。它的基本思想是：从源点出发，每次选择距离源点最近的顶点，更新源点到其他顶点的最短路径。
弗洛伊德算法：
弗洛伊德算法是一种用于求解最短路径的算法，它可以在一个有向图中求出从一个顶点到其他所有顶点的最短路径。它的基本思想是：从源点出发，每次选择距离源点最近的顶点，更新源点到其他顶点的最短路径。它的优点是可以处理负权边，但是它的时间复杂度是O(n^3)。
Bellman-Ford算法：
Bellman-Ford算法是一种用于求解最短路径的算法，它可以在一个有向图中求出从一个顶点到其他所有顶点的最短路径。它的基本思想是：从源点出发，每次选择距离源点最近的顶点，更新源点到其他顶点的最短路径。它的优点是可以处理负权边，而且它的时间复杂度是O(mn)，其中m是边的数量，n是顶点的数量。
典型最短路径算法，用于计算一个节点到其他节点的最短路径。
基本原理：逐遍的对图中每一个边去迭代计算起始点到其余各点的最短路径，执行N-1遍，最终得到起始点到其余各点的最短路径。（N为连通图结点数）
SPFA算法：
SPFA算法是一种用于求解最短路径的算法，它可以在一个有向图中求出从一个顶点到其他所有顶点的最短路径。它的基本思想是：从源点出发，每次选择距离源点最近的顶点，更新源点到其他顶点的最短路径。它的优点是可以处理负权边，而且它的时间复杂度是O(mn)，其中m是边的数量，n是顶点的数量。它的缺点是它可能会出现负环，所以在使用SPFA算法之前，需要先检测图中是否存在负环。
spfa跑的比较kuai