Advertisement
informaticage

Dijkstra implementation C++

Apr 17th, 2023 (edited)
3,318
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.02 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <queue>
  4. #include <utility>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. #define DISTANCE_INITIALIZATION_VALUE -1
  10.  
  11. void add_edge_directed(vector<vector<pair<long long, long long>>> &G,
  12.                        long long u, long long v, long long weight) {
  13.   G.at(u).push_back(make_pair(v, weight));
  14.   // G.at(v).push_back(make_pair(u, weight));
  15. }
  16.  
  17. class Compare {
  18.  public:
  19.   // Ringraziamo l'umile dipendente cicciottello
  20.   // per aver scoperto la necessitá di una inspiegabile parentesi tonda
  21.   bool operator()(pair<long long, long long> &lhs,
  22.                   pair<long long, long long> &rhs) {
  23.     return lhs.second > rhs.second;
  24.   }
  25. };
  26.  
  27. int main() {
  28.   freopen("input.txt", "r", stdin);
  29.   freopen("output.txt", "w", stdout);
  30.  
  31.   long long V, E;
  32.   cin >> V >> E;
  33.   vector<vector<pair<long long, long long>>> G(V, vector<pair<long long, long long>>());
  34.  
  35.   long long source, destination;
  36.   cin >> source >> destination;
  37.   // Per gli indici che partono da 1
  38.   // source--;
  39.   // destination--;
  40.  
  41.   for (long long edge = 0; edge < E; edge++) {
  42.     long long u, v, w;
  43.     cin >> u >> v >> w;
  44.     // Per gli indici che partono da 1
  45.     // u--;
  46.     // v--;
  47.     add_edge_directed(G, u, v, w);
  48.   }
  49.  
  50.   // Shortest path
  51.   priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, Compare> queue;
  52.  
  53.   queue.push(make_pair(source, 0));
  54.  
  55.   vector<bool> visited(V, false);
  56.   vector<long long> distances(V, DISTANCE_INITIALIZATION_VALUE);
  57.  
  58.   while (!queue.empty()) {
  59.     pair<long long, long long> curr = queue.top();
  60.     queue.pop();
  61.  
  62.     if (!visited.at(curr.first)) {
  63.       visited.at(curr.first) = true;
  64.       distances.at(curr.first) = curr.second;
  65.  
  66.       for (pair<long long, long long> neighbour : G.at(curr.first)) {
  67.         if (!visited.at(neighbour.first)) {
  68.           queue.push(
  69.               make_pair(neighbour.first, curr.second + neighbour.second));
  70.         }
  71.       }
  72.     }
  73.   }
  74.  
  75.   cout << distances.at(destination);
  76.   return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement