mohammedehab2002

Untitled

Dec 9th, 2020
621
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<pair<int,int> > v[200005];
  4. long long s[200005];
  5. bool adj[200005];
  6. int cnt[200005];
  7. int main()
  8. {
  9.    
  10.     freopen("hide.in", "r", stdin);
  11.     int n,m;
  12.     scanf("%d%d",&n,&m);
  13.     for (int i=1;i<=n;i++)
  14.     {
  15.         scanf("%I64d",&s[i]);
  16.         adj[i]=1;
  17.     }
  18.     while (m--)
  19.     {
  20.         int a,b,c;
  21.         scanf("%d%d%d",&a,&b,&c);
  22.         if (s[a]+c<s[b] || s[b]+c<s[a])
  23.         {
  24.             printf("-1\n");
  25.             return 0;
  26.         }
  27.         adj[a]&=(s[b]+c!=s[a]);
  28.         adj[b]&=(s[a]+c!=s[b]);
  29.         v[a].push_back({b,c});
  30.         v[b].push_back({a,c});
  31.     }
  32.     int tot=0;
  33.     for (int i=1;i<=n;i++)
  34.     {
  35.         if (adj[i])
  36.         {
  37.             tot++;
  38.             for (auto p:v[i])
  39.             cnt[p.first]+=(p.second==s[i]);
  40.         }
  41.     }
  42.     for (int i=1;i<=n;i++)
  43.     {
  44.         if (cnt[i]==tot)
  45.         {
  46.             bool ok=1;
  47.             for (auto p:v[i])
  48.             ok&=(p.second>=s[p.first]);
  49.             if (ok)
  50.             {
  51.                 printf("%d",i);
  52.                 return 0;
  53.             }
  54.         }
  55.     }
  56.     printf("-1");
  57. }
RAW Paste Data