题目传送门:P2136 拉近距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
在之前有写过spfa做的题《[NOIP2009]最优贸易(分层图论 + SPFA最长路) – ErikTse Runtime》,不过那道题比较复杂,本题是一道纯模板题。
思路
直接spfa,有几个点需要注意。
- 这里是单向图,根据题意,需要对d[1][N]和d[N][1]取小。
- 注意判环,方法是如果一个点走了N次那么一定存在环。
- 可以用exit(0)来使整个程序结束。
- spfa与dijkstra不同,需要让queue全部更新完才能得到正确的答案,而不是第一次走到终点就作为答案。
- 注意inq数组不要漏了。
- 注意每次spfa需要初始化。
- 注意题目给的w要取相反数作为权值(当然你减去权值也行)。
代码
#include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define int long long using namespace std; const int maxn = 1e3 + 10, inf = 1e10; typedef pair<int, int> PII; vector<PII> g[maxn];//{点,权值} int N, M; int spfa(int s,int t) { int cnt[maxn], d[maxn]; for(int i = 1;i <= N; ++ i)cnt[i] = 0,d[i] = inf; bitset<maxn> inq; queue<int> q; q.push(s);inq[s] = 1;d[s] = 0; while(!q.empty()) { int x = q.front();q.pop();inq[x] = 0; cnt[x] ++; if(cnt[x] > N) { printf("Forever love\n"); exit(0); } for(auto i : g[x]) { int nx = i.fi, ew = i.se; if(d[nx] > d[x] + ew) { d[nx] = d[x] + ew; if(!inq[nx]){q.push(nx);inq[nx] = 1;} } } } //全部完成之后d的值才是正确的 return d[t]; } signed main() { cin >> N >> M; while(M --) { int x, y, w;scanf("%lld %lld %lld",&x, &y, &w); g[x].pb({y, -w}); } printf("%lld\n",min(spfa(1,N), spfa(N, 1))); }
Comments NOTHING