宁波个人做网站,网页设计怎么把图片放在指定位置,做网站的公司合肥,呼家楼网站建设题目背景某天#xff0c;奇异博士在纽约圣所研究维山帝之书时#xff0c;发现了连接不同多元宇宙的传送门网络......题目描述经研究#xff0c;奇异博士发现每个传送门都有固定的 “时间代价”—— 正数表示双向通行#xff08;往返时间代价相同均为正值#xff09;#… 题目背景某天奇异博士在纽约圣所研究维山帝之书时发现了连接不同多元宇宙的传送门网络......题目描述经研究奇异博士发现每个传送门都有固定的 “时间代价”—— 正数表示双向通行往返时间代价相同均为正值负数表示单向通行从起点到终点的时间代价为负值。当存在一条从主宇宙出发最终返回主宇宙的路径且总时间代价减少时就会引发时间悖论旅行者可以通过循环该路径让时间无限倒流。请判断某次奇异博士规划的路线中是否存在这样的时间悖论路径。注意奇异博士当前所处的纽约圣所是编号为 1 的主宇宙且各多元宇宙是互通的。输入格式第一行包含整数T表示测试用例数量。每个测试用例的第一行包含两个整数 n 和 m分别表示多元宇宙的数量编号 1~n和传送门的数量。接下来 m 行每行包含三个整数a, b, c, 表示一个传送门若c ≥ 0:该传送门双向通行从 a 到 b 和从 b 到 a 的时间代价均为 c若c 0:该传送门单向通行仅能从 a 到 b时间代价为 c输出格式对于每个测试用例若存在引发时间悖论的路径输出 “YES”否则输出 “NO”。输入输出样例输入2
3 3
1 2 1
2 3 2
3 1 -4
3 3
1 2 1
2 3 2
3 1 4输出 YES
NO说明/提示对于全部的测试点保证1 ≤ T ≤ 101 ≤ n ≤ 2×1031 ≤ m ≤ 4×10^31 ≤ a,b ≤n−10^4 ≤ c ≤1 0^4解题思路判断是否存在从主宇宙节点1出发并返回的路径且总时间代价为负时间减少这样的路径会导致时间悖论。这个问题等价于在图中检测是否存在从节点1可达的负权环。可以使用SPFA算法来检测负权环。使用邻接表存储图结节点1距离为0其他节点距离为无穷大使用队列进行松弛操作如果某个节点被松弛的次数超过节点总数n说明存在负权环。检测到负权环 → 输出YES存在时间悖论未检测到负权环 → 输出NO不存在时间悖论。解决代码
#include iostream
#include vector
#include queue
#include climits
using namespace std;struct Edge {int to;int cost;
};bool hasNegativeCycle(int n, vectorvectorEdge graph) {vectorint dist(n1, INT_MAX);vectorint count(n1, 0);vectorbool inQueue(n1, false);queueint q;dist[1] 0;q.push(1);inQueue[1] true;while (!q.empty()) {int u q.front();q.pop();inQueue[u] false;for (const Edge e : graph[u]) {int v e.to;int cost e.cost;if (dist[u] ! INT_MAX dist[u] cost dist[v]) {dist[v] dist[u] cost;if (!inQueue[v]) {q.push(v);inQueue[v] true;count[v];if (count[v] n) {return true;}}}}}return false;
}int main() {int T;cin T;while (T--) {int n, m;cin n m;vectorvectorEdge graph(n1);for (int i 0; i m; i) {int a, b, c;cin a b c;if (c 0) {graph[a].push_back({b, c});graph[b].push_back({a, c});} else {graph[a].push_back({b, c});}}if (hasNegativeCycle(n, graph)) {cout YES endl;} else {cout NO endl;}}return 0;
}
