Advertisement
Guest User

Untitled

a guest
Jan 29th, 2020
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.38 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef pair<int, int> ii;
  6. typedef vector<int> vi;
  7. typedef vector<vi> vvi;
  8. typedef vector<ii> vii;
  9.  
  10. int
  11. main() {
  12. int n;
  13. cin >> n;
  14. vector<vii> adjList(n, vii());
  15. vector<bool> hasPower(n, false);
  16. double INF = 1000000000;
  17. vector<double> dist(n, INF);
  18. vi topo;
  19. queue<int> q;
  20. vi in(n, 0);
  21.  
  22. for (int i = 0; i < n - 1; i++) {
  23. int u, v, w;
  24. cin >> u >> v >> w;
  25. u--; v--;
  26. adjList[v].push_back(ii(u, w));
  27. in[u]++;
  28. int power;
  29. cin >> power;
  30. if (power) hasPower[i] = true;
  31. }
  32.  
  33. for (int i = 0; i < n; i++) {
  34. int start;
  35. cin >> start;
  36. if (start != -1) dist[i] = 1.0 / start;
  37. }
  38.  
  39. for (int i = 0; i < n; i++) {
  40. if (in[i] == 0) {
  41. q.push(i);
  42. }
  43. }
  44.  
  45. while (!q.empty()) {
  46. int u = q.front();
  47. q.pop();
  48. topo.push_back(u);
  49. for (int i = 0; i < adjList[u].size(); i++) {
  50. int v = adjList[u][i].first;
  51. in[v]--;
  52. if (in[v] == 0) {
  53. q.push(v);
  54. }
  55. }
  56. }
  57. // for (int i = 0; i < topo.size(); i++) {
  58. // cout << topo[i] << ' ';
  59. // }
  60. for (int i = 0; i < topo.size(); i++) {
  61. int u = topo[i];
  62. if (dist[u] == INF) continue;
  63. if (adjList[u].size() == 0) cout << 1 / dist[u];
  64. for (int j = 0; j < adjList[u].size(); j++) {
  65. int v = adjList[u][j].first;
  66. int w = adjList[u][j].second;
  67. dist[v] = min(dist[v], dist[u] / (100.0 / w));
  68. }
  69. }
  70.  
  71. return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement