fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector <pair <int,long long> > g[2010];
  4. long long dist[2010];
  5. void solve(){
  6.     int n,m,k;
  7.     cin>>n>>m>>k;
  8.     for (int i=0; i<=n; i++) g[i].clear();
  9.     for (int i=1; i<=m; i++){
  10.         int pos,val;
  11.         cin>>pos>>val;
  12.         g[pos].push_back({0,-val});
  13.         g[0].push_back({pos,val});
  14.     }
  15.     for (int i=1; i<=k; i++){
  16.         int u,v,d;
  17.         cin>>u>>v>>d;
  18.         g[u].push_back({v,d});
  19.         g[v].push_back({u,d});
  20.     }
  21.     for (int i=0; i<=n; i++) dist[i]=0;
  22.     bool relaxed=0;
  23.     for (int iters=0; iters<=n; iters++){
  24.         relaxed=0;
  25.         for (int i=0; i<=n; i++){
  26.             for (pair <int,long long> j:g[i]){
  27.                 if (dist[i]+j.second<dist[j.first]){
  28.                     dist[j.first]=dist[i]+j.second;
  29.                     relaxed=1;
  30.                 }
  31.             }
  32.         }
  33.         if (!relaxed){
  34.             cout<<"YES\n";
  35.             return;
  36.         }
  37.     }
  38.     cout<<"NO\n";
  39. }
  40. int main(){
  41.     ios_base::sync_with_stdio(0); cin.tie(0);
  42.     int t; cin>>t;
  43.     while (t--) solve();
  44. }
Success #stdin #stdout 0.01s 5476KB
comments (?)
stdin
copy 
1
6 2 7
1 3
2 8
1 3 2
2 4 1
3 5 1
4 5 1
1 5 3
3 6 0
1 6 1
stdout
copy 
NO
https://ideone.com/IV7SVA
language:
C++ (gcc 8.3)
created:
315 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!