fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. int n, m, h;
  7. vector< int > generator;
  8. vector< int > line[1003];
  9.  
  10. void Read()
  11. {
  12.     cin>>n>>m>>h;
  13.     for (int i=0; i<m; i++)
  14.     {
  15.         int tmp;
  16.         cin>>tmp;
  17.         generator.push_back(tmp);
  18.     }
  19.     for (int i=0; i<h; i++)
  20.     {
  21.         int a, b;
  22.         cin>>a>>b;
  23.         line[a].push_back(b);
  24.         line[b].push_back(a);
  25.     }
  26. }
  27.  
  28. int weak[1003];
  29.  
  30. void Init()
  31. {
  32.     for (int i=0; i<n; i++)
  33.     {
  34.         weak[i] = 1003;
  35.     }
  36. }
  37.  
  38. int check[1003];
  39. int trans[1003];
  40. void Reset()
  41. {
  42.     for (int i=0; i<n; i++)
  43.     {
  44.         check[i] = 0;
  45.         trans[i] = -1;
  46.     }
  47. }
  48.  
  49. void BFS(int u)
  50. {
  51.     check[u] = 1;
  52.     queue<int> q;
  53.     q.push(u);
  54.     trans[u] = 0;
  55.     while(!q.empty())
  56.     {
  57.         int u = q.front();
  58.         q.pop();
  59.         for (int i=0; i<line[u].size(); i++)
  60.         {
  61.             int v = line[u][i];
  62.             if (check[v] == 0)
  63.             {
  64.                 q.push(v);
  65.                 check[v] = 1;
  66.                 trans[v] = trans[u] + 1;
  67.             }
  68.         }
  69.     }
  70. }
  71.  
  72. void CheckWeak()
  73. {
  74.     for (int i=0; i<n; i++)
  75.     {
  76.         if (trans[i]!=-1)
  77.         {
  78.             if (trans[i]<weak[i])
  79.             {
  80.                 weak[i] = trans[i];
  81.             }
  82.         }
  83.     }
  84. }
  85.  
  86. void OUT()
  87. {
  88.     int p = 0;
  89.     for (int i=1; i<n; i++)
  90.     {
  91.         if (weak[i] > weak[p])
  92.         {
  93.             p = i;
  94.         }
  95.     }
  96.     cout<<p;
  97. }
  98.  
  99. void Test()
  100. {
  101.     for (int i=0; i<n; i++)
  102.     {
  103.         cout<<check[i]<<" ";
  104.     }
  105.     cout<<endl;
  106.     for (int i=0; i<n; i++)
  107.     {
  108.         cout<<trans[i]<<" ";
  109.     }
  110.     cout<<endl;
  111.     for (int i=0; i<n; i++)
  112.     {
  113.         cout<<weak[i]<<" ";
  114.     }
  115. }
  116.  
  117.  
  118.  
  119. int main()
  120. {
  121. //    freopen("input.txt", "r", stdin);
  122.     Read();
  123.     Init();
  124.     for (int i=0; i<m; i++)
  125.     {
  126.         Reset();
  127.         BFS(generator[i]);
  128.         CheckWeak();
  129.     }
  130.     OUT();
  131. //    test();
  132.     return 0;
  133. }
Success #stdin #stdout 0s 15280KB
comments (?)
stdin
copy 
6 3 5
0 5 2
0 1
1 2
4 5
3 5
0 2
stdout
copy 
1
https://ideone.com/C1yMXV
v- P145SUMH - ROUND 5H - Hệ thống điện
language:
C++ (gcc 8.3)
created:
5 years 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!