Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <cstdio>
- #include <vector>
- using namespace std;
- typedef long long lld;
- int T = 0;
- struct Vertex {
- vector< int > neighs;
- lld limit;
- double cur;
- int T_out, index;
- };
- inline bool operator <(const Vertex &a, const Vertex &b) {
- return a.T_out > b.T_out;
- }
- Vertex *nodes;
- void DFS(int vertex) {
- for (unsigned i = 0; i < nodes[vertex].neighs.size(); i++)
- DFS(nodes[vertex].neighs[i]);
- nodes[vertex].T_out = ++T;
- }
- int main() {
- freopen("input.txt", "r", stdin); //
- int N, K;
- scanf("%d%d", &N, &K);
- nodes = new Vertex [N];
- for (int i = 0; i < N; i++) {
- scanf("%lld%lf", &nodes[i].limit, &nodes[i].cur);
- nodes[i].index = i;
- }
- for (int i = 0; i < K; i++) {
- int F, T;
- scanf("%d%d", &F, &T);
- F--;
- T--;
- nodes[F].neighs.push_back(T);
- }
- int start, target;
- lld start_adding;
- scanf("%d%lld%d", &start, &start_adding, &target);
- start--;
- target--;
- DFS(start);
- sort(nodes, nodes + N);
- nodes[0].cur += start_adding;
- for (int i = 0; i < target; i++) {
- if (nodes[i].cur > nodes[i].limit) {
- double adding = (nodes[i].cur - nodes[i].limit) / nodes[i].neighs.size();
- for (unsigned j = 0; j < nodes[i].neighs.size(); i++)
- nodes[nodes[i].neighs[j]].cur += adding;
- }
- }
- printf("%.4lf\n", min(nodes[target].cur, static_cast< double > (nodes[target].limit)));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement