## 边的存储方式

1、vector储存

```const int N = 1e5 + 7; //节点数
const int M = 5e5 + 7; //路径数
const ll INF = 1e18;
int u[M], v[M], w[M];
ll d1[N], d2[N];//d1正向图，d2反向图
struct Node {
int v;
ll cost;
bool operator < (Node b)const {
return cost > b.cost;
}
};
vector<Node> e[N];
int n, m;

int main() {
for (int i = 1; i <= m; ++i) {
e[u[i]].push_back(Node{ v[i], w[i] });
e[v[i]].push_back(Node{ u[i], w[i] });
}
return 0;
}```

2、前向星保存

```const int N = 5e3 + 7; //节点数
const int M = 5e3 + 7; //路径数
const int INF = 0x3f3f3f3f;
int head[N], tot = 0;//前向星变量
struct Node {
//int u;
int v, w, next;
} edge[M << 1];

void add(int u, int v, int w) {
tot++;
//edge[tot].u = u;
edge[tot].v = v;
edge[tot].w = w;
}```

## dijkstra算法

```#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}

const int N = 1e5 + 7; //节点数
const int M = 5e5 + 7; //路径数
const ll INF = 1e18;
int u[M], v[M], w[M];
ll d1[N]; //d1正向图
struct Node {
int v;
ll cost;
bool operator < (Node b)const {
return cost > b.cost;
}
};
vector<Node> e[N];
int n, m, st, ed;

void dijkstra(int s, ll d[]) {
priority_queue<Node>  pq;
fill(d, d + N, INF);
d[s] = 0;
pq.push(Node{ s,0 });
while (!pq.empty()) {
Node    x = pq.top();
pq.pop();
if (d[x.v] < x.cost)    continue; //原先这个节点花费更少 跳过
for (auto it : e[x.v]) {
if (d[it.v] > x.cost + it.cost) {
d[it.v] = x.cost + it.cost;
pq.push(Node{ it.v,d[it.v] });
}
}
}
}

int main() {
for (int i = 1; i <= m; ++i) {
e[u[i]].push_back(Node{ v[i], w[i] });
e[v[i]].push_back(Node{ u[i], w[i] });
}
st = 1;
dijkstra(st, d1);
for (int i = 1; i <= n; ++i) {
printf("%d->%d : %lld\n", st, i, d1[i]);
}
return 0;
}```

## spfa算法

```//判断负环
#include <bits/stdc++.h>
using namespace std;

inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}

const int N = 2e3 + 5;
const int INF = 0x3f3f3f3f;
struct Node {
int v, w;
};
int n, m, w, st, ed;
vector<Node>e[N];
int d[N];
bool vis[N];
queue<int>q;
int times[N];//记录松弛次数

int spfa(int s) {
memset(vis, 0, sizeof(vis));
memset(d, 0x3f, sizeof(d));
memset(times, 0, sizeof(times));
while (!q.empty())  q.pop();//多组数据，处理前要全部清空
q.push(s);
vis[s] = 1;
d[s] = 0;
times[s] = 1;
while (!q.empty()) {
int now = q.front();
q.pop();
vis[now] = 0;
for (auto it : e[now])
if (d[it.v] > d[now] + it.w) {
d[it.v] = d[now] + it.w;
++times[it.v];//松弛次数加1
if (times[it.v] == n) //如果已经有点松弛次数大于n
return 0;        //说明有负环,返回，不需要继续遍历
if (!vis[it.v]) {
q.push(it.v);
vis[it.v] = 1;
}
}
}
return 1;//永远没有点松弛次数大于n，说明无负环
}
int main() {
int T = read();
while (T--) {
for (int i = 1; i <= m; i++) {
int u = read(), v = read(), w = read();
e[u].push_back(Node{ v, w });
e[v].push_back(Node{ u, w });//大于等于0时双向边
}
for (int i = 1; i <= w; ++i) {
int u = read(), v = read(), w = read();
e[u].push_back(Node{ v,-w });
}
st = 1;
bool flag = spfa(st); //调用函数，起点为1
if (flag) {  //不存在负环
puts("NO");
//输出各点最短路
for (int i = 1; i <= n; ++i)
printf("%d->%d : %d\n", st, i, d[i]);
}
else   puts("YES");
for (int j = 1; j <= n; j++)
e[j].clear();//清空
}
return 0;
}```

## floyd算法

```// Floyd算法 O(N^3)  任意两点最短路
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}

const int N = 310; //节点数
int dp[N][N]; //表示从i->j的最短路径
int n, m;

void floyd() {
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; ++i)    dp[i][i] = 0;
//dp初始化为邻接矩阵
for (int i = 1; i <= m; ++i) {
int u = read(), v = read(), w = read();
dp[u][v] = min(dp[u][v], w);
}
for (int k = 1; k <= n; ++k) //经过编号不超过k的从i->k的最短路径
//dp[k,i,j]=min(dp[k-1][i][j],dp[k-1][i][k] + dp[k-1][k][j])，
//k是阶段，i，j是附加状态，再和背包问题一样利用滚动数组节省第一维
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}

int main() {
floyd();
//输出
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
printf("%d ", dp[i][j]);
puts("");
}
return 0;
}
```

## 最小生成树，kruskal算法和prim算法

```//kruskal 适用于稀疏图  O(n+m*log2(m))
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}

const int N = 6e3 + 7; //节点
const int M = 6e3 + 7; //路径数
int n, m;
struct Edge {
int u, v, w;
bool operator <(const Edge tmp) const {
return w < tmp.w;
}
}edge[M];
int father[N];
ll ans = 0; //最小生成树的花费和

int find(int root) {
int son = root;
while (root != father[root])
root = father[root];
while (son != root) { //路径压缩
int temp = father[son];
father[son] = root;
son = temp;
}
return root;
}

void kruskal() {
for (int i = 1; i <= m; i++) {
int u = edge[i].u, v = edge[i].v;
int x = find(u), y = find(v);
if (x != y) {
father[x] = y;
ans += edge[i].w;
}
}
}
int main() {
int T = read();
while (T--) {
for (int i = 1; i <= n; ++i)
father[i] = i;
for (int i = 1; i <= m; ++i)
sort(edge + 1, edge + 1 + m);
kruskal();
}
return 0;
}```
```//无向图最小生成树
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}

const int N = 3e3 + 7;
const int INF = 0x3f3f3f3f;
int e[N][N], vis[N], dis[N];
int n, m;
ll ans;
//prim适合稠密图 O(n^2)，特别是完全图最小生成树的求解
void prim() {
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
for (int i = 1; i < n; ++i) {
int x = 0;
for (int j = 1; j <= n; ++j)
if (!vis[j] && (x == 0 || dis[j] < dis[x]))
x = j;
vis[x] = 1;
for (int j = 1; j <= n; ++j)//用u点更新  刚刚新拓展的边
if (!vis[j])    dis[j] = min(dis[j], e[x][j]);
}
}

int main() {
//构建邻接矩阵
memset(e, 0x3f, sizeof(e));
for (int i = 0; i <= n; ++i)    e[i][i] = 0;
for (int i = 1; i <= m; ++i) {
int x = read(), y = read(), z = read();
e[x][y] = e[y][x] = min(e[x][y], z);
}
//求最小生成树
prim();
for (int i = 2; i <= n; ++i)    ans += dis[i];
printf("%lld\n", ans);
return 0;
}```

## 拓扑排序

```#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}

const int N = 1e3 + 7;
int in[N];
int n, m; // 节点数，边数
vector<int>edge[N];

void topsort() {
queue<int>q; //如果要按字典序，使用最小堆即可
for (int i = 1; i <= n; i++)  //n  节点的总数
if (in[i] == 0) q.push(i);  //将入度为0的点入队列
vector<int>ans;   //ans 为拓扑序列
while (!q.empty()) {
int p = q.front(); q.pop(); // 选一个入度为0的点，出队列
ans.push_back(p);
for (int i = 0; i < edge[p].size(); i++) {
int y = edge[p][i];
in[y]--;
if (in[y] == 0)
q.push(y);
}
}
if (ans.size() == n) {
for (int i = 0; i < ans.size(); i++)
printf("%d ", ans[i]);
printf("\n");
}
else printf("No Answer!\n");   //  ans 中的长度与n不相等，就说明无拓扑序列

}

int main() {