Guest User

Untitled

a guest
Nov 12th, 2019
87
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4.  
  5. using namespace std;
  6.  
  7. const long long INF = 6000 * (long long)1e15;
  8. struct edge {
  9. int s;
  10. int e;
  11. int w;
  12.  
  13. edge(int s_, int e_, int w_) {
  14. s = s_;
  15. e = e_;
  16. w = w_;
  17. }
  18.  
  19. };
  20.  
  21. long long d[2005][2005];
  22.  
  23.  
  24. long long min(long long a, long long b) {
  25. if (a > b) return b;
  26. return a;
  27. }
  28.  
  29. vector <edge> edges;
  30. vector<vector<pair<int, long long>>> g;
  31.  
  32. vector <bool> used;
  33. void dfs(int v) {
  34. used[v] = true;
  35. for (auto u : g[v]) {
  36. if (!used[u.first]) {
  37. dfs(u.first);
  38. }
  39. }
  40. }
  41.  
  42. int main() {
  43. int n, m, s;
  44. cin >> n >> m >> s;
  45. s--;
  46. used.assign(n, false);
  47. g.assign(n, {});
  48. for (int i = 0; i < m; i++) {
  49. int st, e;
  50. long long w;
  51. cin >> st >> e >> w;
  52. st--; e--;
  53. edges.emplace_back(st, e , w);
  54. g[st].emplace_back(e, w);
  55.  
  56. }
  57. for (int i = 0; i < n; i++) {
  58. for (int j = 0; j <= n; j++) {
  59. d[i][j] = INF;
  60. }
  61. }
  62. d[s][0] = 0;
  63.  
  64. vector <int> cycles;
  65. for (int k = 1; k <= n; k++) {
  66. for (int i = 0; i < n; i++) {
  67. d[i][k] = d[i][k - 1];
  68. }
  69. for (int v = 0; v < n; v++) {
  70. if (d[v][k - 1] == INF) continue;
  71. for (auto u : g[v]) {
  72. if (d[u.first][k] > d[v][k - 1] + u.second) {
  73. if (k == n) {
  74. cycles.push_back(u.first);
  75. }
  76. //cout << "s: " << v << " e: " << u.first << " d[v]: " << d[v][k - 1] << " d[e]: " << d[u.first][k] << " w: " << u.second << endl;
  77. d[u.first][k] = d[v][k - 1] + u.second;
  78.  
  79. }
  80. }
  81. }
  82. }
  83. vector <long long> ans(n, INF);
  84.  
  85. for (int i = 0; i < n; i++) {
  86. for (int j = 0; j < n; j++) {
  87. ans[i] = min(ans[i], d[i][j]);
  88. }
  89. }
  90.  
  91. for (int v : cycles) {
  92. if (!used[v]) {
  93. dfs(v);
  94. }
  95. }
  96. for (int v = 0; v < n; v++) {
  97. if (used[v]) {
  98. cout << "-\n";
  99. continue;
  100. }
  101. if (ans[v] == INF) {
  102. cout << "*\n";
  103. continue;
  104. }
  105. cout << ans[v] << '\n';
  106. }
  107. /* for (int i = 0; i < n; i++) {
  108. cout << "v: " << i << " d: " << d[i][n - 1] << endl;
  109. }*/
  110.  
  111.  
  112.  
  113. }
RAW Paste Data