#include #include #include #define MAX 123456789 using namespace std; struct node{ int vertex; int weight; int sum; }; struct compare{ bool operator()(const node &a, const node &b){ return a.sum > b.sum; } }; int main(){ int T, N, M, W; cin >> T; for(int tc=0 ; tc> N >> M >> W; vector map[567]; int save[567][567] = {0,}; for(int i=0 ; i> s >> e >> t; node temp; temp.vertex = e; temp.weight = t; map[s].push_back(temp); temp.vertex = s; map[e].push_back(temp); } for(int i=0 ; i> s >> e >> t; node temp; temp.vertex = e; temp.weight = -t; map[s].push_back(temp); } //// input end // check every node for(int sn=1 ; sn<=N ; sn++){ priority_queue,compare> pq; int dist[567]; for(int i=1 ; i<=N ; i++) dist[i] = MAX; for(auto it : map[sn]){ it.sum = it.weight; if(dist[it.vertex] > it.sum){ dist[it.vertex] = it.sum; pq.push(it); } } while(!pq.empty()){ node t = pq.top();pq.pop(); if(dist[t.vertex] < t.sum) continue; if(dist[t.vertex] < 0) continue; for(auto it : map[t.vertex]){ if(dist[it.vertex] > t.sum + it.weight){ node temp = it; temp.sum = t.sum + it.weight; dist[it.vertex] = temp.sum; pq.push(temp); } } } for(int i=1 ; i<=N ; i++){ if(i==sn) save[sn][i] = 0; else save [sn][i] = dist[i]; } } bool check = 0; for(int i=1 ; i<=N ; i++){ for(int j=i ; j<=N ; j++){ if(i==j) continue; if(save[i][j]+save[j][i] < 0) check= 1; } } if(check) cout << "YES\n"; else cout << "NO\n"; } }

제출 #139539

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: