#ifndef _CRT_SECURE_NO_WARNINGS #define _CRT_SECURE_NO_WARNINGS #endif #include #include #include #include #include using namespace std; int dist[501]; unordered_map road[501]; int main() { ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); freopen("input.txt", "r", stdin); int t, T, i, j; cin >> t; int INF = 1 << 30; while (t--) { int n, m, w; cin >> n; cin >> m >> w; for (int i = 1; i <= n; i++) { dist[i] = INF; } while (m--) { int n1, n2, c; cin >> n1 >> n2 >> c; if (road[n1].find(n2) == road[n1].end() || c < road[n1][n2]) { road[n1][n2] = c; road[n2][n1] = c; } } while (w--) { int n1, n2, c; cin >> n1 >> n2 >> c; c = c * -1; if (road[n1].find(n2) == road[n1].end() || c < road[n1][n2]) { road[n1][n2] = c; } } dist[1] = 0; for (int i = 0; i < n-1; i++) { for (int j = 1; j <= n; j++) { for (const auto& mi : road[j]) { if (mi.second < 0 && dist[j] == INF) { dist[j] = mi.second; } else if (dist[j] == INF) continue; if (dist[j] + mi.second < dist[mi.first]) dist[mi.first] = dist[j] + mi.second; } } } bool mi = false; for (int i = 1; i <= n; i++) { if (dist[i] < 0) { mi = true; break; } } set loop; for (int j = 1; j <= n; j++) { for (const auto& mi : road[j]) { if (dist[j] == INF) continue; if (dist[j] + mi.second < dist[mi.first]) { dist[mi.first] = dist[j] + mi.second; loop.insert(mi.first); } } } if (mi || loop.size()) cout << "YES\n"; else cout << "NO\n"; } return 0; }

제출 #105161

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: