NO.95十六届蓝桥杯备战|图论基础-单源最短路|负环|BF判断负环|SPFA判断负环|邮递员送信|采购特价产品|拉近距离|最短路计数(C++)

如果图中存在负环，那么有可能不存在最短路。

从起点找别的点的最短距离很简单，直接跑各种最短路算法均可。
但是从别的点回到起点的最短路，如果直接求时间复杂度巨⾼。思考⼀件事：

• 假设从某⼀点z，到达起点的最短路径为：z->y->x->s；
• 那么反过来就是s->x->y->z的最短路径。
  因此，仅需对原图的所有图建⽴⼀个"反图"，然后跑⼀遍最短路即可。这就是建"反图"的技巧

#include <bits/stdc++.h>
using namespace std;const int N = 1e3 + 10;int n, m;
int e[N][N];int dist[N];
bool st[N];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()
{ios::sync_with_stdio(false);cin.tie(0);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();int ret = 0;for (int i = 1; i <= n; i++) ret += dist[i];//反图for (int i = 1; i <= n; i++)for (int j = i+1; 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;
}

看数据范围，所有的最短路算法均可解决，这⾥使⽤BF算法。
⽆需建图，只⽤把所有的边存下来。注意是⽆向边，所以要存两次，空间也要开两倍。
在所有边上做⼀次bf算法，输出结果即可

#include <bits/stdc++.h>
using namespace std;const int N = 110, M = 1010;int n, m, s, t;
double x[N], y[N];struct node
{int a, b;double c;
}e[M];double calc(int i, int j)
{double dx = x[i] - x[j];double dy = y[i] - y[j];return sqrt(dx * dx + dy * dy);
}double dist[N];void bf()
{for (int i = 1; i <= n; i++) dist[i] = 1e10;dist[s] = 0;for (int i = 1; i < n; i++){for (int j = 1; j <= m; j++){int a = e[j].a, b = e[j].b;double c = e[j].c;if (dist[a] + c < dist[b]){dist[b] = dist[a] + c;}if (dist[b] + c < dist[a]){dist[a] = dist[b] + c;}}}
}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;e[i].a = a; e[i].b = b; e[i].c = calc(a, b);}cin >> s >> t;bf();printf("%.2lf\n", dist[t]);return 0;
}

bf算法判断负环即可。但要注意⼀下细节：

1. 题⽬中给的是距离w是能缩⼩的数，因此存边的时候，应该存成相反数；
2. 爱情是双向奔赴的，我们要在1->n和n->1两种情况⾥⾯选择最⼩值

#include <bits/stdc++.h>
using namespace std;const int N = 1e3 + 10, M = 1e4 + 10;int n, m;
struct node
{int a, b, c;
}e[M];int dist[N];bool bf(int s)
{memset(dist, 0x3f, sizeof dist);dist[s] = 0;bool flg;for (int i = 1; i <= n; i++){flg = false;for (int j = 1; j <= m; j++){int a = e[j].a, b = e[j].b, c = e[j].c;if (dist[a] + c < dist[b]){flg = true;dist[b] = dist[a] + c;}}if (flg == false) return flg;}return flg;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++){cin >> e[i].a >> e[i].b >> e[i].c;e[i].c = -e[i].c;}int ret;bool st = bf(1);if (st){cout << "Forever love" << endl;return 0;}ret = dist[n];st = bf(n);if (st){cout << "Forever love" << endl;return 0;}cout << min(ret, dist[1]) << endl;return 0;
}

解法⼀：bfs+动态规划

• 因为边权全都相等，所以可以⽤bfs找出最短路；
• 在bfs找最短路的过程中，更新最短路的条数。
  动态规划：

1. 状态表⽰：设 f[i] 表⽰从起点⾛到 i 点的最短路的条数。
2. 状态转移⽅程： f[i] += f[prev] 。
   其中 prev 表⽰ i 点的所有前驱，但是要注意是通过最短路过来的前驱。
3. 填表顺序：按照bfs的顺序填表。
   解法⼆：dijkstra算法+动态规划
   这种解法更通⽤，因为即使边权不相等，也可以⽤dj算法

#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
const int N = 1e6 + 10, M = 2e6 + 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);queue<int> q;q.push(1);dist[1] = 0;f[1] = 1;while (q.size()){auto a = q.front(); q.pop();for (auto b : edges[a]){if (dist[a] + 1 < dist[b]){dist[b] = dist[a] + 1;f[b] = f[a];q.push(b);}else if (dist[a] + 1 == dist[b]){f[b] = (f[b] + f[a]) % MOD;}}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++){int a, b; cin >> a >> b;edges[a].push_back(b);edges[b].push_back(a);}bfs();for (int i = 1; i <= n; i++) cout << f[i] << endl;return 0;
}

#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
const int N = 1e6 + 10, M = 2e6 + 10, MOD = 100003;int n, m;
vector<int> edges[N];int dist[N];
bool st[N];
int f[N];void dijkstra()
{memset(dist, 0x3f, sizeof dist);priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1});dist[1] = 0;f[1] = 1;while (heap.size()){auto t = heap.top(); heap.pop();int a = t.second;if (st[a]) continue;st[a] = true;for (auto b : edges[a]){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);cin >> n >> m;for (int i = 1; i <= m; i++){int a, b; cin >> a >> b;edges[a].push_back(b);edges[b].push_back(a);}dijkstra();for (int i = 1; i <= n; i++) cout << f[i] << endl;return 0;
}