fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct Friendship {
  8.     int u, v;
  9. };
  10.  
  11. void solve() {
  12.     int n, m;
  13.     cin >> n >> m;
  14.  
  15.     vector<int> a(n + 1);
  16.     for (int i = 1; i <= n; i++) {
  17.         cin >> a[i];
  18.     }
  19.  
  20.     vector<Friendship> edges(m);
  21.     vector<int> degree(n + 1, 0);
  22.  
  23.     for (int i = 0; i < m; i++) {
  24.         cin >> edges[i].u >> edges[i].v;
  25.         degree[edges[i].u]++;
  26.         degree[edges[i].v]++;
  27.     }
  28.  
  29.     if (m % 2 == 0) {
  30.         cout << 0 << "\n";
  31.         return;
  32.     }
  33.  
  34.     int min_unhappiness = 1e9;
  35.  
  36.     for (int i = 1; i <= n; i++) {
  37.         if (degree[i] % 2 != 0) {
  38.             min_unhappiness = min(min_unhappiness, a[i]);
  39.         }
  40.     }
  41.  
  42.     for (int i = 0; i < m; i++) {
  43.         int u = edges[i].u;
  44.         int v = edges[i].v;
  45.  
  46.         if (degree[u] % 2 == 0 && degree[v] % 2 == 0) {
  47.             min_unhappiness = min(min_unhappiness, a[u] + a[v]);
  48.         }
  49.     }
  50.  
  51.     cout << min_unhappiness << "\n";
  52. }
  53.  
  54. int main() {
  55.     ios_base::sync_with_stdio(false);
  56.     cin.tie(NULL);
  57.  
  58.     int t;
  59.     if (cin >> t) {
  60.         while (t--) {
  61.             solve();
  62.         }
  63.     }
  64.     return 0;
  65. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
4
1 0
1
3 1
2 1 3
1 3
5 5
1 2 3 4 5
1 2
1 3
1 4
1 5
2 3
5 5
1 1 1 1 1
1 2
2 3
3 4
4 5
5 1
stdout
copy 
0
2
3
2
https://ideone.com/cTNH8C
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!