图的概念
图：点--边
度->有向图（入度，出度）|| 无向图（度）
自环：若一条边的两个顶点为同一顶点，则此边称作自环。
路径：从任何一个点出发，随意在图上走，走出来的序列叫路径。| 简单路径（一条路径，每个点最多只能走一次）
特殊的图
1）没有环的无向图：树-->无向，连通，无环 || n个点 n-1条边
只有无向无环：很多个树-->森林
只有连通无环（有向）：(连通的DAG)/有向树
只有无向连通：。。。
2）有向图的树：外向树，内向树
外向：所有边的方向都是从根向外指
内向：所有边的方向都是从外向根的方向指
3）树的扩展：章鱼图/基环树：环上每个点连出去的部分为一棵树 || n个点的章鱼图n条边
树变成章鱼图加一条边 || 章鱼图删掉环上一条边变成树
4）仙人掌图：边仙人掌，点仙人掌
边仙人掌：每条边最多在一个环上
点仙人掌：每个点最多在一个环上
点仙人掌一定是边仙人掌
5）DAG(Directed Acyclic Graph)：有向无环图
6）二分图
无向图
所有的点划为左边一部分，右边一部分，保证图当中所有的边都是从左边的一个点连到右边的一个点
树一定是二分图
图的储存方法
邻接矩阵 ---------- 边表
优点：O(1)检查 || O(m)的内存
缺点：内存大，重边只能记一条 || 检查
最短路
单源最短路问题：求一点到所有点的最短路
多源最短路问题：求多点到所有点的最短路
最短路中的三角不等式：
dis[i][k]+dis[k][j]>=dis[i][j]
松弛操作
求最短路过程中
if dis[i][k]+k->j（k到j的长度）<dis[i][j]
dis[i][j]==dis[i[[k]+k->
通过一条边来更新最短路的操作叫做松弛操作
最短路问题
1）Floyd
多源最短路算法
求任意连点之间的最短路
时间复杂度O(n3) || 空间复杂度O(n2)
处理范围n<=200~500
2）Dijkstra
单元最短路算法（前提：边权>=0）
求一个点到其他点的最短路
| dis | 1 | 2 | 3 | 4 |
| 初始化 | 0 | ∞ |
∞ |
∞ |
（1-->1的最短路是0）
DJ堆优化3）Dijkstra+Heap
4）Bellman-Ford
5）SPFA
1 //By:Komorebi_03 2 #include<bits/stdc++.h> 3 using namespace std; 4 #define int long long 5 const int INF = 2147483647; 6 const int N = 1e6+5; 7 int n,m,s,e_cnt,dis[N],vis[N],head[N]; 8 struct node{ 9 int v; 10 int w; 11 int nxt; 12 }e[N]; 13 inline int read() 14 { 15 int x=0,f=1;char ch=getchar(); 16 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 17 while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} 18 return x*f; 19 } 20 21 void add(int u,int v,int w) 22 { 23 e[++e_cnt].v=v; 24 e[e_cnt].w=w; 25 e[e_cnt].nxt=head[u]; 26 head[u]=e_cnt; 27 } 28 29 void SPFA() 30 { 31 queue<int> q; 32 for (int i=1;i<=n;i++) 33 { 34 dis[i]=INF; 35 vis[i]=0; 36 } 37 q.push(s); 38 dis[s]=0; 39 vis[s]=1; 40 while(!q.empty()) 41 { 42 int u=q.front(); 43 q.pop(); 44 vis[u]=0; 45 for (int i=head[u];i;i=e[i].nxt) 46 { 47 int v=e[i].v; 48 if(dis[v]>dis[u]+e[i].w) 49 { 50 dis[v]=dis[u]+e[i].w; 51 if(vis[v]==0) 52 { 53 vis[v]=1; 54 q.push(v); 55 } 56 } 57 } 58 } 59 } 60 61 signed main() 62 { 63 n=read(); 64 m=read(); 65 s=read(); 66 for (int i=1;i<=m;i++) 67 { 68 int u=read(); 69 int v=read(); 70 int w=read(); 71 add(u,v,w); 72 } 73 SPFA(); 74 for (int i=1;i<=n;i++) 75 { 76 if(s==i) 77 cout<<0<<" "; 78 else 79 cout<<dis[i]<<" "; 80 } 81 return 0; 82 }