本编的知识内容由小编手搓，以及资料均来自比特官网~
OJ题来源：洛谷
OJ题名：邮递员送信
OJ题归属：图论基础【单源最短路】
解题算法：邻接矩阵存图 + 算法四选一、这里用的是常规版dijkstra算法
💡经验总结：
话说是只需要 n – 1 循环即可求出 dist 数组的最终值，但是在这题里，如果在dijkstra算法里面求最终结果，只循环 n – 1 次是累加不出来最终正确的结果的，所以，我们最好循环 n 次哦！
这里还用了一个做题技巧，就是存反图，这里是从起点走到 i 位置，再从 i 位置走回到起点位置，然后在开始其他趟的进行，这里我们如果不建反图的话，解决从 i 位置走到起点位置是比较麻烦的，如果我们建反图，我们再跑一遍dijkstra算法就行了，这波操作就属于：将“从不同位置走到同一终点”问题转化成了“单源最短路问题”！
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e3;
int n, m;
int e[N][N]; // 邻接矩阵存图
int dist[N];
bool st[N];
int ret;
void dijkstra()
{
// 初始化
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[1] = 0;
for (int i = 1; i <= n; i++)
{
int a = 0;
for (int j = 1; j <= n; j++)
if (!st[j] && dist[j] < dist[a])
a = j;
st[a] = true;
for (int b = 1; b <= n; b++)
{
int c = e[a][b];
if (dist[a] + c < dist[b])
dist[b] = dist[a] + c;
}
}
}
int main()
{
cin >> n >> m;
memset(e, 0x3f, sizeof e);
for (int i = 1; i <= m; i++)
{
int a, b, c; cin >> a >> b >> c;
// 重边
e[a][b] = min(e[a][b], c);
}
dijkstra();
for (int i = 1; i <= n; i++) ret += dist[i];
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
swap(e[i][j], e[j][i]);
dijkstra();
for (int i = 1; i <= n; i++) ret += dist[i];
cout << ret << endl;
return 0;
}
OJ题来源：洛谷
OJ题名：采购特价商品
OJ题归属：图论基础【单源最短路】
解题算法：vector存图 + 算法四选一、这里用的是常规版dijkstra算法
—存图时要计算边权值，然后正常跑一下 dijkstra 算法。
💡经验总结：
这里的 dist 数组是 double 类型的，我们在给 dist 数组初始化的时候，不能再用memset进行 dist 数组的初始化了，要老老实实用 for 循环初始化~
memset 是字节级填充工具，只适合字节类型、或 4 字节 int 特殊无穷大场景； double/long double 遵循 IEEE754 浮点编码，逐字节填充无法得到预期数值，不能用 memset 初始化无穷大。 只有 memset(arr, 0, sizeof(arr)) 可以安全清零浮点数组。
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef pair<int, double> PID;
const int N = 110;
int n, m;
vector<PID> edges[N];
struct node
{
int x, y;
}Coordinates[N]; // 存坐标
double dist[N];
bool st[N];
int tbegin, tend;
void dijkstra()
{
// 初始化
for (int i = 0; i <= n; i++) dist[i] = 1e10;
dist[tbegin] = 0;
for (int i = 1; i <= n; i++)
{
// 找“min”
int a = 0;
for (int j = 1; j <= n; j++)
if (!st[j] && dist[j] < dist[a])
a = j;
st[a] = true;
for (auto& e : edges[a])
{
int b = e.first; double c = e.second;
if (dist[a] + c < dist[b])
{
dist[b] = dist[a] + c;
}
}
}
printf("%.2lf\\n", dist[tend]);
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
int x, y; cin >> x >> y;
Coordinates[i].x = x; Coordinates[i].y = y;
}
cin >> m;
for (int i = 1; i <= m; i++)
{
int u, v; cin >> u >> v;
int x1 = Coordinates[u].x, y1 = Coordinates[u].y;
int x2 = Coordinates[v].x, y2 = Coordinates[v].y;
double x = x1 – x2;
double y = y1 – y2;
double w = sqrt(x * x + y * y);
edges[u].push_back({ v, w });
edges[v].push_back({ u, w });
}
cin >> tbegin >> tend;
dijkstra();
return 0;
}
OJ题来源：洛谷
OJ题名：拉近距离
OJ题归属：图论基础【单源最短路】
解题算法：可以解决负环的算法二选一、这里用的是 Bellman-Ford 算法
题目细节：
📌存边权存的是题目给的边权的相反数
📌爱情是双向的，以 1 为起点走到 n ；以 n 为起点走到 1 .
💡经验总结：
💡判断负环时，dist 数组已经更新好了，因为已经执行了 n – 1 轮，前面执行的 n – 1 轮都是为了第 n 轮判断负环~ 而前 n – 1 轮是可以把 dist 数组完全更新的。
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, m;
vector<PII> edges[N];
int dist[N];
// BF 判断是否有负环，构造成带参的可以重复利用，
// 判断负环不论结果，dist 数组已经是以起点 s 更新好的了
bool bf(int s)
{
// 初始化
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
bool flag;
for (int i = 1; i <= n; i++)
{
flag = false;
for (int a = 1; a <= n; a++)
{
for (auto& e : edges[a])
{
int b = e.first, c = e.second;
if (dist[a] + c < dist[b])
{
dist[b] = dist[a] + c;
flag = true;
}
}
}
if (flag == false) return flag;
}
return flag;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int s, t, w; cin >> s >> t >> w;
edges[s].push_back({ t, -w });
}
int ret;
if (bf(1))
{
cout << "Forever love" << endl;
return 0;
}
ret = dist[n];
if (bf(n))
{
cout << "Forever love" << endl;
return 0;
}
ret = min(ret, dist[1]);
cout << ret << endl;
return 0;
}
OJ题来源：洛谷
OJ题名：最短路计数
OJ题归属：图论基础【单源最短路】
解题算法：基于单元最短路算法实现的动态规划；由于要先确定一点已完成，且该题边权相等，可用最短路算法：bfs、dijkstra、spfa。如果边权不相等，可用最短路算法：dijkstra。本编实现了 bfs 与 堆优化版的dijkstra 两种。
题目细节：
📌重边要存
📌卡了输入输出那块的时间复杂度，要瘦身或者用 scanf/printf
📌bfs 与 dijkstra 两种实现时，对 st 数组有不同的要求，要应算法而变
💡经验总结：
💡这题的难点是动态规划的填表顺序，基于单源最短路的填表顺序，该题动态规划状态转移方程的更新是跟着松弛操作的判断同步的。dist[a] + 1 < dist[b] 的条件是第一次遍历到 b 点，而且 a 点已经确定了，dist[a] 的确定意味着 f[a] 的确定，f[b] = f[a]；dist[a] + 1 == dist[b] 的条件是 不是第一次遍历到 b 点，最短路的条数要开始相加了，f[b] = f[a] + f[b]。
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, MOD = 100003;
int n, m;
vector<int> edges[N];
int dist[N];
bool st[N];
int f[N];
void bfs()
{
// 初始化
memset(dist, 0x3f, sizeof dist);
f[1] = 1;
dist[1] = 0;
queue<int> q;
q.push(1);
// 不需要 st[i] = true ,因为这个点不只被遍历一次，打上标记就只能遍历一次了
while (q.size())
{
auto a = q.front(); q.pop();
for (auto& e : edges[a])
{
int b = e;
if (dist[a] + 1 < dist[b])
{
// 第一次遍历到 b
dist[b] = dist[a] + 1;
f[b] = f[a];
q.push(b);
}
else if (dist[a] + 1 == dist[b])
{
// 不是第一次遍历到
f[b] = (f[a] + f[b]) % MOD;
}
}
}
}
void dijkstra()
{
// 初始化
memset(dist, 0x3f, sizeof dist);
f[1] = 1;
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; //小根堆
heap.push({ 0, 1 });
while (heap.size())
{
auto p = heap.top(); heap.pop();
int a = p.second;
if (st[a]) continue; // 已经确定过最短路的点就不用在更新一次了
// 不然，在 else if 那会多加
st[a] = true;
for (auto& e : edges[a])
{
int b = e;
if (dist[a] + 1 < dist[b])
{
dist[b] = dist[a] + 1;
f[b] = f[a];
heap.push({ dist[b], b });
}
else if (dist[a] + 1 == dist[b])
{
f[b] = (f[a] + f[b]) % MOD;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y; cin >> x >> y;
edges[x].push_back(y);
edges[y].push_back(x);
}
//bfs();
dijkstra();
for (int i = 1; i <= n; i++) cout << f[i] << endl;
return 0;
}
