SHARE
TWEET

Untitled

a guest May 19th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <queue>
  4. #include <vector>
  5. #include <cstring>
  6. using namespace std;
  7.  
  8. const int MAXN = 1000;
  9. int MAX_VAL;
  10.  
  11. struct State
  12. {
  13.     int to, price;
  14.     State( int t, int p ): to(t), price(p) {}
  15.     bool operator<( const State& s ) const
  16.     {
  17.         if( price == s.price )
  18.             return to < s.to;
  19.         return price > s.price;
  20.     }
  21. };
  22.  
  23. int N, M, start;
  24. vector <State> v[MAXN];
  25.  
  26. void input()
  27. {
  28.     scanf("%d %d", &N, &M);
  29.     int x, y, w;
  30.     for( int i = 0; i < M; i++ )
  31.     {
  32.         scanf("%d %d %d", &x, &y, &w);
  33.         v[x-1].push_back(State(y-1, w));
  34.         v[y-1].push_back(State(x-1, w));
  35.     }
  36.     scanf("%d", &start);
  37.     start--;
  38. }
  39.  
  40. int dist[MAXN];
  41. bool used[MAXN];
  42. int pred[MAXN];
  43.  
  44. void print_path( int vertex )
  45. {
  46.     if( pred[vertex] == -1 )
  47.     {
  48.         printf("%d ", vertex+1);
  49.         return;
  50.     }
  51.     print_path(pred[vertex]);
  52.     printf("%d ", vertex+1);
  53. }
  54.  
  55. void dijkstra()
  56. {
  57.     memset(dist, 63, sizeof(dist));
  58.     MAX_VAL = dist[0];
  59.     memset(pred, -1, sizeof(pred));
  60.     used[start] = 1;
  61.  
  62.  
  63.     priority_queue <State> pq;
  64.     for( int i = 0; i < v[start].size(); i++ )
  65.     {
  66.         dist[v[start][i].to] = v[start][i].price;
  67.         pred[v[start][i].to] = start;
  68.         pq.push(State(v[start][i].to, v[start][i].price));
  69.     }
  70.  
  71.     while( !pq.empty() )
  72.     {
  73.         int vertex = pq.top().to;
  74.         int price = pq.top().price;
  75.         pq.pop();
  76.         if( used[vertex] )
  77.             continue;
  78.         used[vertex] = 1;
  79.  
  80.         for( int i = 0; i < v[vertex].size(); i++ )
  81.         {
  82.             int curr_vertex = v[vertex][i].to;
  83.             int curr_price = v[vertex][i].price;
  84.             if( !used[curr_vertex] && dist[curr_vertex] > dist[vertex] + v[vertex][i].price )
  85.             {
  86.                 dist[curr_vertex] = dist[vertex] + v[vertex][i].price;
  87.                 pred[curr_vertex] = vertex;
  88.                 pq.push(State(curr_vertex, dist[curr_vertex]));
  89.             }
  90.         }
  91.     }
  92.  
  93.     for( int i = 0; i < N; i++ )
  94.         if( dist[i] == MAX_VAL )
  95.             printf("There is no path between %d and %d.\n", start+1, i+1);
  96.         else
  97.         {
  98.             printf("Length of path between %d and %d is: %d\n", start+1, i+1, dist[i]);
  99.             printf("Path is: ");
  100.             print_path(i);
  101.             printf("\n");
  102.         }
  103. }
  104.  
  105. int main()
  106. {
  107.     input();
  108.     dijkstra();
  109.  
  110.     return 0;
  111. }
  112. /**
  113. Test 1:
  114. 6 9
  115. 1 2 1
  116. 1 3 2
  117. 2 3 1
  118. 2 4 3
  119. 3 4 1
  120. 4 6 3
  121. 2 6 7
  122. 5 2 8
  123. 6 5 1
  124. 1
  125.  
  126. Test 2: The following test shows Dijkstra doesn't work correctly when there is an edge with negative cost. In such case, we can use
  127. the algorithm of Floyd-Warshall instead.
  128. 3 3
  129. 1 2 2
  130. 2 3 -100
  131. 1 3 1
  132. 1
  133. **/
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top