题目
题目背景
我是源点，你是终点。我们之间有负权环。 ——小明
题目描述
在小明和小红的生活中，有 N 个关键的节点。有 M 个事件，记为一个三元组 (Si,Ti,Wi)，表示从节点 Si 有一个事件可以转移到 Ti，事件的效果就是使他们之间的距离减少 Wi。
这些节点构成了一个网络，其中节点 1 和 N 是特殊的，节点 1 代表小明，节点 N 代表小红，其他代表进展的阶段。所有事件可以自由选择是否进行，但每次只能进行当前节点邻接的。请你帮他们写一个程序，计算出他们之间可能的最短距离。
输入格式
第一行，两个正整数 N,M。
之后 M 行，每行 3 个空格隔开的整数 Si,Ti,Wi。
输出格式
一行，一个整数表示他们之间可能的最短距离。如果这个距离可以无限缩小，输出Forever love。
输入输出样例
输入 #1
3 3
1 2 3
2 3 -1
3 1 -10输出 #1
-2说明/提示
对于 20% 数据，N≤10，M≤50。
对于 50% 数据，N≤300，M≤5000。
对于 100% 数据，1≤N≤103，1≤M≤104，∣Wi∣≤100，保证从节点 1 到 2…N 有路径，从节点 N 到 1…N−1 有路径。
思路
这道题很显然是一道单源最短路的题目，通过观察题目，我们可以得出以下信息：
是单向图
计算的是小红与小明之间的最短距离，这意味着可以是小红到小明，也可以是小明到小红
题目有明显的负环，需要输出
Forever love题目中的边权不是相加是相减，为了避免麻烦改代码，可以对边权取反来建图。
那么这道题是非常良心的👍，出题人没有卡SPFA，所以我们使用SPFA来求解。
对于SPFA来找负环，可以建立一个 数组，我们定义 𝑐𝑛𝑡[𝑖] 表示点 𝑖 距离源点经过的边数 每次 𝑖 → 𝑗 转移的时候 𝑐𝑛𝑡[𝑗] = 𝑐𝑛𝑡[𝑖] + 1 如果有点的 𝑐𝑛𝑡 大于等于 𝑛 时说明有负环，就直接输出 Forever love
多说无益，我们看代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// N是数组大小，INF用来给dis赋初始值，即极大值
const int N = 1000 + 5, INF = 100000000;
int n, m;
vector<vector<pair<int, int>>> e(N); // 比较奇葩的STL写法，不喜欢的可以写结构体
ll dis[N]; // 记录从起点到任意点的最短距离的数组
bool vis[N]; // 判断任意点是否在队列中
int cnt[N]; // 记录任意点的出队次数，用来判断负环
void spfa(int s) {
// SPFA的初始化
fill(dis + 1, dis + n + 1, INF);
fill(vis + 1, vis + n + 1, false);
fill(cnt + 1, cnt + n + 1, 0);
dis[s] = 0, vis[s] = true;
queue<int> q;
q.emplace(s);
// SPFA
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = false; // 标记点u不在队列中了
for (pair<int, int> tmp : e[u]) { //适配C++14的写法
int v, w;
tie(v, w) = tmp;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1; // 找负环
if (cnt[v] >= n) {
cout << "Forever love\n"; // 有负环
exit(0);
}
if (!vis[v]) {
vis[v] = true; // 点v在队列中了
q.emplace(v); // 把点v加入队列
}
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int u, v, w;
cin >> u >> v >> w;
e[u].emplace_back(v, -w); // 对边权取反，方便处理
}
spfa(1); // 从小明到小红
ll ans1 = dis[n];
spfa(n); // 从小红到小明
ll ans2 = dis[1];
cout << min(ans1, ans2) << "\n"; // 对两个答案取较小值
return 0;
}代码提交结果如下：
