Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef pair<int, int> ii;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<ii> vii;
- int
- main() {
- int n;
- cin >> n;
- vector<vii> adjList(n, vii());
- vector<bool> hasPower(n, false);
- double INF = 1000000000;
- vector<double> dist(n, INF);
- vi topo;
- queue<int> q;
- vi in(n, 0);
- for (int i = 0; i < n - 1; i++) {
- int u, v, w;
- cin >> u >> v >> w;
- u--; v--;
- adjList[v].push_back(ii(u, w));
- in[u]++;
- int power;
- cin >> power;
- if (power) hasPower[i] = true;
- }
- for (int i = 0; i < n; i++) {
- int start;
- cin >> start;
- if (start != -1) dist[i] = 1.0 / start;
- }
- for (int i = 0; i < n; i++) {
- if (in[i] == 0) {
- q.push(i);
- }
- }
- while (!q.empty()) {
- int u = q.front();
- q.pop();
- topo.push_back(u);
- for (int i = 0; i < adjList[u].size(); i++) {
- int v = adjList[u][i].first;
- in[v]--;
- if (in[v] == 0) {
- q.push(v);
- }
- }
- }
- // for (int i = 0; i < topo.size(); i++) {
- // cout << topo[i] << ' ';
- // }
- for (int i = 0; i < topo.size(); i++) {
- int u = topo[i];
- if (dist[u] == INF) continue;
- if (adjList[u].size() == 0) cout << 1 / dist[u];
- for (int j = 0; j < adjList[u].size(); j++) {
- int v = adjList[u][j].first;
- int w = adjList[u][j].second;
- dist[v] = min(dist[v], dist[u] / (100.0 / w));
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement