?

題目背景

某天，奇異博士在紐約圣所研究維山帝之書時，發現了連接不同多元宇宙的傳送門網絡......

題目描述

經研究，奇異博士發現每個傳送門都有固定的 “時間代價”—— 正數表示雙向通行（往返時間代價相同均為正值），負數表示單向通行（從起點到終點的時間代價為負值）。

當存在一條從主宇宙出發，最終返回主宇宙的路徑，且總時間代價減少時，就會引發時間悖論（旅行者可以通過循環該路徑讓時間無限倒流）。

請判斷某次奇異博士規劃的路線中是否存在這樣的時間悖論路徑。

注意：奇異博士當前所處的紐約圣所是編號為 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 ≤ 10

• 1 ≤ n ≤ 2×103，1 ≤ m ≤ 4×10^3

• 1 ≤ 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, vector<vector<Edge>>& graph) {vector<int> dist(n+1, INT_MAX);vector<int> count(n+1, 0);vector<bool> inQueue(n+1, false);queue<int> 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;vector<vector<Edge>> graph(n+1);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;
}

?

?