Advertisement
Um_nik

Untitled

Sep 14th, 2014
337
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. typedef long long lld;
  7.  
  8. int T = 0;
  9.  
  10. struct Vertex {
  11.     vector< int > neighs;
  12.     lld limit;
  13.     double cur;
  14.     int T_out, index;
  15. };
  16.  
  17. inline bool operator <(const Vertex &a, const Vertex &b) {
  18.     return a.T_out > b.T_out;
  19. }
  20.  
  21. Vertex *nodes;
  22.  
  23. void DFS(int vertex) {
  24.     for (unsigned i = 0; i < nodes[vertex].neighs.size(); i++)
  25.         DFS(nodes[vertex].neighs[i]);
  26.     nodes[vertex].T_out = ++T;
  27. }
  28.  
  29. int main() {
  30.     freopen("input.txt", "r", stdin); //
  31.  
  32.     int N, K;
  33.     scanf("%d%d", &N, &K);
  34.     nodes = new Vertex [N];
  35.     for (int i = 0; i < N; i++) {
  36.         scanf("%lld%lf", &nodes[i].limit, &nodes[i].cur);
  37.         nodes[i].index = i;
  38.     }
  39.     for (int i = 0; i < K; i++) {
  40.         int F, T;
  41.         scanf("%d%d", &F, &T);
  42.         F--;
  43.         T--;
  44.         nodes[F].neighs.push_back(T);
  45.     }
  46.     int start, target;
  47.     lld start_adding;
  48.     scanf("%d%lld%d", &start, &start_adding, &target);
  49.     start--;
  50.     target--;
  51.  
  52.     DFS(start);
  53.     sort(nodes, nodes + N);
  54.  
  55.     nodes[0].cur += start_adding;
  56.     for (int i = 0; i < target; i++) {
  57.         if (nodes[i].cur > nodes[i].limit) {
  58.             double adding = (nodes[i].cur - nodes[i].limit) / nodes[i].neighs.size();
  59.             for (unsigned j = 0; j < nodes[i].neighs.size(); i++)
  60.                 nodes[nodes[i].neighs[j]].cur += adding;
  61.         }
  62.     }
  63.     printf("%.4lf\n", min(nodes[target].cur, static_cast< double > (nodes[target].limit)));
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement