单源最短路
概念
dijkstra实现（解决不了负权值）
P3371 【模板】单源最短路径（弱化版） - 洛谷
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;typedef pair<int, int> PII;
const int N = 1e4 + 10;
const int INF = 2147483647;
vector<PII> edge[N];//i后面接的点j，和到j的距离
bool st[N];//是否已经确定是最优解
int dist[N];//起点到个点的最小值
int n, m, s;void dijksta()
{for (int i = 1; i < n; i++){int a = 0;for (int i = 1; i <= n; i++)//找目前dist中的最小值{if (!st[i] && dist[i] < dist[a])a = i;//没有被确定最优，且最小}st[a] = true;for (auto& ch : edge[a])//更新：松弛操作{int v = ch.first, w = ch.second;if (dist[v] > dist[a] + w){dist[v] = dist[a] + w;}}}for (int i = 1; i <= n; i++)cout << dist[i] << " ";
}int main()
{cin >> n >> m >> s;for (int i = 1; i <= m; i++){int x, y, z;cin >> x >> y >> z;edge[x].push_back({ y,z });}for (int i = 0; i <= n; i++)dist[i] = INF;//如果要初始化的数字太大，那就用不了memsetdist[s] = 0;//初始化起点dijksta();return 0;
}P4779 【模板】单源最短路径（标准版） - 洛谷
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;int n, m,s;
vector<PII> edge[N];
bool st[N];
int dis[N];
priority_queue<PII,vector<PII>,greater<PII>> q;void dijkstra()
{memset(dis, 0x3f, sizeof(dis));dis[s] = 0;q.push({ 0,s });//先存距离，后存结点，因为，greater会根据第一个数据first进行小跟堆排序while (q.size()){auto t = q.top(); q.pop();int a = t.second;if (st[a])continue;st[a] = true;for (auto& x : edge[a]){int b = x.first, c = x.second;if (dis[a] + c < dis[b]){dis[b] = dis[a] + c;q.push({ dis[b], b });}}}for (int i = 1; i <= n; i++)cout << dis[i] << " ";
}int main()
{cin >> n >> m>>s;for (int i = 1; i <= m; i++){int a, b, c; cin >> a >> b >> c;edge[a].push_back({ b,c });}dijkstra();return 0;
}
BF算法（）可以解决负权以及最短路不存在的情况（负环）
负环：每次转一圈，权值就减小
P3371 【模板】单源最短路径（弱化版） - 洛谷
#include<iostream>
#include<vector>using namespace std;
const int N = 1e4 + 10;
const int INF = 2147483647;typedef pair<int, int> PII;
vector<PII> edge[N];
int dis[N];
int n, m , s;void BF()
{for (int i = 1; i <= n; i++)dis[i] = INF;dis[s] = 0;for (int i = 1; i < n; i++)//n-1条边，那就n-1次就好{bool judge = false;//没有了松弛操作，就退出for (int j = 1; j <= n; j++)//遍历全部{if (dis[j] == INF)continue;//if (dis[j] + b < dis[a]),这一步+，会让超出int范围变成负数，for (auto& x : edge[j]){int a = x.first, b = x.second;if (dis[j] + b < dis[a]){dis[a] = dis[j] + b;judge = true;//有松弛操作}}}if (judge == false)break;}for (int i = 1; i <= n; i++){if (dis[i] != INF)cout << dis[i] << " ";else cout << INF << " ";}
}int main()
{cin >> n >> m >> s;for (int i = 1; i <= m; i++){int x, y, z; cin >> x >> y >> z;edge[x].push_back({ y,z });}BF();
}
spfa算法：用队列对BF算法进行优化
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e4 + 10;
const int INF = 2147483647;typedef pair<int, int> PII;
vector<PII> edge[N];
int dis[N];
int n, m , s;
queue<PII> q;
bool st[N];void BF()
{for (int i = 1; i <= n; i++)dis[i] = INF;dis[s] = 0;q.push({ s,0 });st[s] = true;while (q.size()){auto t = q.front(); q.pop();int a = t.first, b = t.second;for (auto& x : edge[a]){int y = x.first, z = x.second;if (dis[a] + z < dis[y]){dis[y] = dis[a] + z;if(!st[y])q.push({ y, dis[y] });st[y] = true;}}}for (int i = 1; i <= n; i++){if (dis[i] != INF)cout << dis[i] << " ";else cout << INF << " ";}
}int main()
{cin >> n >> m >> s;for (int i = 1; i <= m; i++){int x, y, z; cin >> x >> y >> z;edge[x].push_back({ y,z });}BF();
}
标准版跑不过：是因为很容易创造数据针对spfa
只是对松弛的进行操作，松弛-进队。
负环P3385 【模板】负环 - 洛谷
bf算法实现
#include<iostream>
#include<cstring>
using namespace std;const int N = 2e3 + 10;
const int M = 3e3 + 10;int T, n, m;
int pos;//记录边的个数
struct node
{int u, v, w;
}edge[M*2];
int dis[N];bool bf()
{memset(dis, 0x3f3f3f3f, sizeof(dis));dis[1] = 0;//出发点bool flag;for (int i = 1; i <= n; i++){flag = false;for (int j = 1; j <= pos; j++){int a = edge[j].u, b = edge[j].v, c = edge[j].w;if (dis[a] == 0x3f3f3f3f)continue;if (dis[a] + c < dis[b]){dis[b] = dis[a] + c;flag = true;}}if (flag == false)return flag;//如果在n-1次到来前退出循环，说明，没有负环，返回false}return flag;//如果n-1次循环都没有返回false,那么就一定存在负环
}int main()
{cin >> T;while (T--){cin >> n >> m;pos = 0;for (int i = 1; i <= m; i++){int x, y, z; cin >> x >> y >> z;++pos;edge[pos].u = x, edge[pos].v = y, edge[pos].w = z;if (z >= 0){++pos;edge[pos].u = y, edge[pos].v = x, edge[pos].w = z;}}if (bf())cout << "YES" << endl;else cout << "NO" << endl;}
}spfa算法实现
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>using namespace std;
typedef pair<int, int> PII;const int N = 2e3 + 10;
const int M = 3e3 + 10;int t, n, m;
vector<PII> edge[N];
int dis[N];
bool st[N];
int cnt[N];bool spfa()
{//清除memset(dis, 0x3f, sizeof(dis));//一开始无穷大memset(cnt, 0, sizeof(cnt));//0memset(st, false, sizeof(st));//false//初始化queue<int> q;q.push(1);//推入1//初始化dis[1] = 0;st[1] = true;cnt[1] = 0;while (q.size()){int x = q.front(); q.pop();st[x] = false;for (auto& ch : edge[x]){int a = ch.first, b = ch.second;if (dis[x] + b < dis[a]){dis[a] = dis[x] + b;if (!st[a]){q.push(a);st[a] = true;}cnt[a] = cnt[x] + 1;if (cnt[a] >= n)return true;}}}return false;
}int main()
{cin >> t;while (t--){//清除for (int i = 1; i <= n; i++)edge[i].clear();cin >> n >> m;//输入for (int i = 1; i <= m; i++){int a, b, c; cin >> a >> b >> c;edge[a].push_back({ b,c });if (c >= 0){edge[b].push_back({ a,c });}}//大框架if (spfa())cout << "YES" << endl;else cout << "NO" << endl;}
}总结
例题
P1629 邮递员送信 - 洛谷（推反图）
#include<iostream>
#include<cstring>
using namespace std;const int N = 1e3 + 10;
int n, m;
int edge[N][N];
int dis[N];
bool st[N];void dijkstra()
{memset(dis, 0x3f, sizeof(dis));memset(st, false, sizeof(st));dis[1] = 0;for (int i = 1; i <= n; i++)//n次操作{int t = 0;for (int j = 1; j <= n; j++){if (!st[j] && dis[j] < dis[t])t = j;//未标记加《dis[t]}st[t] = true;for (int j = 1; j <= n; j++){if (!st[j] && edge[t][j]+dis[t] < dis[j]){dis[j] = edge[t][j] + dis[t];}}}
}int main()
{cin >> n >> m;memset(edge, 0x3f, sizeof(edge));for (int i = 1; i <= m; i++){int x, y, z;cin >> x >> y >> z;edge[x][y] = min(edge[x][y], z);}dijkstra();int ret = 0;for (int i = 1; i <= n; i++)ret += dis[i];//推反图for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (i >= j)continue;swap(edge[i][j], edge[j][i]);}}dijkstra();for (int i = 1; i <= n; i++)ret += dis[i];cout << ret << endl;
}起点和终点的调换，推反图，他每送完一旦就要返回去，那我们第一次算法，从1到其他店的距离之和记为去的距离，也就可以看成单元最短路问题
而回去的时候，把起点和终点进行调换，变成从其他个点到1的距离，进行调换后，也可以看成单源最短路问题
P1744 采购特价商品 - 洛谷
#include<iostream>
#include<cmath>using namespace std;const int N = 110;
const int M = 1010;int x[N], y[N];//店铺的坐标
struct node
{int s;//头int e;//尾double v;//长
}ed[M];//记录边1int n;//how many shops
int m;//通路
int star, en;//起点-终点
double dis[N];//起点到各点的距离double cal(int i, int j)//计算
{double a = x[i] - x[j];double b = y[i] - y[j];return sqrt(a * a + b * b);
}void BF()
{for (int i = 1; i <= n; i++) dis[i] = 1e10;//过大dis[star] = 0;for (int i = 1; i < n; i++)//n-1次操作{for (int j = 1; j <= m; j++)//每个边都遍历一遍{int s = ed[j].s;int e = ed[j].e;double v = ed[j].v;if (dis[s] + v < dis[e]){dis[e] = dis[s] + v;//更新}if (dis[e] + v < dis[s]){dis[s] = dis[e] + v;//更新,重边，没说有向边那就可能存在重边}}}}int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> x[i] >> y[i];}cin >> m;for (int i = 1; i <= m; i++){int a, b; cin >> a >> b;ed[i].s = a, ed[i].e = b;ed[i].v = cal(a, b);}cin >> star >> en;BF();printf("%.2lf", dis[en]);return 0;
}蠢哭了，两点间距离公式，写成减号半天看不出来
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
P2136 拉近距离 - 洛谷
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
const int M = 1e4+10;int n, m;struct node
{int x, y, z;
}e[M];
int dis[N];bool BF(int s)
{memset(dis, 0x3f, sizeof(dis));dis[s] = 0;bool flag = true;for (int i = 1; i <= n; i++){flag = false;for (int j = 1; j <= m; j++){int a = e[j].x, b = e[j].y, c = e[j].z;//老是把这个地方写成i记得改！！！！if (dis[a] + c < dis[b]){dis[b] = dis[a] + c;//更新flag = true;//更新}}if (flag == false)return flag;}return true;
}int main()
{cin >> n >> m;for (int i = 1; i <= m; i++){cin >> e[i].x >> e[i].y >> e[i].z;e[i].z = -e[i].z;}//起点是1//双向的求最小if (BF(1)){cout << "Forever love" << endl;//有负环return 0;}int ret1 = dis[n];//记录//起点是nif (BF(n)){cout << "Forever love" << endl;//有负环return 0;}int ret2 = dis[1];cout << min(ret1, ret2) << endl;
}bf或者spfa
双向求最小，两边都要进行遍历
int a = e[j].x, b = e[j].y, c = e[j].z;//老是把这个地方写成i记得改！！！！
P1144 最短路计数 - 洛谷
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;const int N = 1e6 + 10;
const int M = 2e6 + 10;
const int MOD = 100003;int n, m;
vector<int> edge[M];
int dis[N];
int f[N];void bfs()
{memset(dis, 0x3f, sizeof(dis));//初始化1dis[1] = 0;f[1] = 1;queue<int> q;q.push(1);while (q.size()){int t = q.front(); q.pop();for (auto& ch : edge[t]){int b = ch;if (dis[t] + 1 < dis[b])//第一次{dis[b] = dis[t] + 1;f[b] = f[t];q.push(b);}else if (dis[t] + 1 == dis[b]){f[b] = (f[b]+f[t])% MOD;}}}
}
typedef pair<int, int>PII;
bool st[N];
void dijkstra()
{memset(dis, 0x3f, sizeof(dis));dis[1] = 0;f[1] = 1;priority_queue<PII,vector<PII>,greater<PII>> q;q.push({ 0,1 });while (q.size()){auto t = q.top(); q.pop();int a = t.second;if (st[a])continue;st[a] = true;for (auto& ch : edge[a]){int x = ch;if (dis[a] + 1 < dis[x]){f[x] = f[a];dis[x] = dis[a] + 1;q.push({ dis[x],x });}else if (dis[a] + 1 == dis[x]){f[x] = (f[x] + f[a]) % MOD;}}}
}int main()
{cin >> n >> m;for (int i = 1; i <= m; i++){int x, y; scanf("%d%d", &x, &y);edge[x].push_back(y);edge[y].push_back(x);}/*bfs();*/dijkstra();for (int i = 1; i <= n; i++){printf("%d\n", f[i]);}return 0;
}用bfs和dijkstra算法+动态规划来实现
