【题目来源】https://www.luogu.com.cn/problem/P2850【题目描述】Farmer John 在探索他的农场时发现了许多神奇的虫洞。虫洞的特性非常特殊——它是一个单向通道能将你传送到它的目的地而且时间还会回溯到过去FJ 的每个农场包含 N(1≤N≤500) 块编号为 1∼N 的田地、M(1≤M≤2500) 条双向路径和 W(1≤W≤200) 个虫洞。作为狂热的时间旅行爱好者FJ 希望实现从某块田地出发经过若干路径和虫洞后在初始离开时间之前回到起点。这样或许他能遇见自己 :)为了判断可行性FJ 将提供 F(1≤F≤5) 个农场的完整地图。所有路径通行耗时不超过 10,000 秒虫洞最多能将 FJ 带回 10,000 秒前。【输入格式】第 1 行一个整数 F表示农场数。后续为 F 个农场的数据。每个农场第 1 行三个空格分隔的整数 N田地数, M双向路径数, W虫洞数。第 2∼M1 行每行三个空格分隔的整数 (S,E,T)表示 S 和 E 间有一条耗时 T 秒的双向路径。两块田地间可能存在多条路径。第 M2∼MW1 行每行三个空格分隔的整数 (S,E,T)表示一条从 S 到 E 的单向虫洞可将 FJ 带回 T 秒前。【输出格式】输出 F 行对每个农场若 FJ 能达成目标输出YES否则输出NO。​​​​​​​【输入样例】23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8​​​​​​​【输出样例】NOYES【数据范围】1≤N≤500、1≤M≤2500、1≤W≤200、1≤F≤5【算法分析】● 题目中 road2500每条存 2 条边就是 5000再加 200 虫洞单组最多 5200 条边。所以代码中把 M 设为6005。否则数组越界直接 RE​​​​​​​● Bellman-Ford 算法使用边集数组存图而非邻接表。这是因为 Bellman-Ford 在每一轮迭代中都需要遍历图中全部边执行松弛操作无需查询某个顶点的出边。而邻接表的核心优势是快速获取单个顶点的邻接边但这项能力在 Bellman-Ford 算法中完全用不到。因此邻接表额外的索引结构自然成为冗余。反观边集数组它仅存储每条边自身的信息结构极简恰好适配 Bellman-Ford 算法的执行逻辑。● 包含 n 个顶点的图其最短路径一定是简单路径路径中不会重复经过同一个顶点不含任何环即最多包含 n-1 条边。所以Bellman-Ford 算法最多只需要松弛 n-1 轮。1算法的第 k 轮松弛作用是求出“最多经过 k 条边”能够得到的最短距离。第 1 轮更新仅用 1 条边可达的最短路第 2 轮更新最多 2 条边的最短路以此类推。当完成 n-1 轮松弛后所有简单路径对应的最短距离都已经被更新完成。2如果执行完 n-1 轮之后仍然还有边可以继续松弛就说明图中存在“负环”。即可以不断环绕这个环无限降低路径总权值不存在有限的最短路径。​​​​​​​● 本题为无向图。无向边 u-v 等价于两条方向相反的有向边u → v 与 v → u。因此在使用 Bellman‑Ford 算法的边集数组存图时读入一条无向边需要同时存入这两条有向边才能完整表达双向连通关系。【算法代码】#include bits/stdc.h using namespace std; const int N5e25; const int M6e35; int dis[N]; struct edge { int u,v,w; } e[M]; int n,m; bool bellman(int n,int m) { memset(dis,0,sizeof dis); for(int i1; in; i) { bool flag0; for(int j1; jm; j) { int ue[j].u, ve[j].v, we[j].w; if(dis[v]dis[u]w) { dis[v]dis[u]w; flag1; } } if(!flag) break; } for(int j1; jm; j) { int ue[j].u,ve[j].v,we[j].w; if(dis[v]dis[u]w) { return true; } } return false; } int main() { int T; cinT; while(T--) { int farm,road,hole; cinfarmroadhole; int cnt0; for(int i1; iroad; i) { int u,v,w; cinuvw; e[cnt] {u,v,w}; e[cnt] {v,u,w}; } for(int i1; ihole; i) { int u,v,w; cinuvw; e[cnt] {u,v,-w}; } if(bellman(farm,cnt)) coutYES\n; else coutNO\n; } return 0; } /* in: 2 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 3 2 1 1 2 3 2 3 4 3 1 8 out: NO YES */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/166848957