Advertisement
Josif_tepe

Untitled

Jun 9th, 2022
946
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <stack>
  6. using namespace std;
  7. struct node {
  8.     int A, B, C;
  9.     node(int a, int b, int c) {
  10.         A = a;
  11.         B = b;
  12.         C = c;
  13.     }
  14. };
  15. int main() {
  16.     int n, m;
  17.     cin >> n >> m;
  18.     vector<int> distance(n + 1, 2e9);
  19.     vector<node> graph;
  20.     for(int i = 0; i < m; i++) {
  21.         int a, b, c;
  22.         cin >> a >> b >> c;
  23.         graph.push_back(node(a, b, c));
  24.     }
  25.     int S;
  26.     cin >> S;
  27.    
  28.     distance[S] = 0;
  29.     for(int i = 0; i < n - 1; i++) {
  30.         for(int j = 0; j < m; j++){
  31.             int a =graph[j].A;
  32.             int b = graph[j].B;
  33.             int weight = graph[j].C;
  34.             if(distance[a] != 2e9 and distance[a] + weight < distance[b]) {
  35.                 distance[b] = distance[a] + weight;
  36.             }
  37.             }
  38.     }
  39.     for(int i = 0; i < m; i++) {
  40.         int a= graph[i].A;
  41.         int b = graph[i].B;
  42.         int weight = graph[i].C;
  43.         if(distance[a] != 2e9 and distance[a] + weight < distance[b]) {
  44.             cout << "ima negativen ciklus" << endl;
  45.         }
  46.     }
  47.     for(int i = 0; i < n; i++) {
  48.         cout << distance[i] << " ";
  49.     }
  50.  
  51.     return 0;
  52. }
  53. 5 9
  54. 0 1 4
  55. 0 2 2
  56. 1 2 3
  57. 2 1 1
  58. 1 4 2
  59. 1 3 4
  60. 2 4 3
  61. 2 3 5
  62. 3 4 -5
  63.  
Advertisement
RAW Paste Data Copied
Advertisement