#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] < -12345) 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); } } } //cout << "start node : " << sn << ' '; for(int i=1 ; i<=N ; i++){ if(i==sn) save[sn][i] = 0; else save [sn][i] = dist[i]; //cout << dist[i] << ' '; } //cout << '\n'; } 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; //cout << "check : " << i << ' ' << j << " => "<< save[i][j]+save[j][i] << '\n'; } } if(check) cout << "YES\n"; else cout << "NO\n"; } }

제출 #139550

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: