Advertisement
Guest User

Faster Dijkstra

a guest
Dec 5th, 2019
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. #define MAX_N 30000
  8. #define INFINITY 1000000000
  9.  
  10. int n,m,s,t,numtest;
  11. vector<int> adj[MAX_N];
  12. vector<int> weight[MAX_N];
  13.  
  14. void read_input()
  15. {
  16.   cin >> n >> m >> s >> t;
  17.   for(int i=0; i<n; i++) {
  18.     adj[i].clear();
  19.     weight[i].clear();
  20.   }
  21.   for(int i=0; i<m; i++) {
  22.     int u,v,w;
  23.     cin >> u >> v >> w;
  24.    
  25.     adj[u].push_back(v);
  26.     weight[u].push_back(w);
  27.  
  28.     adj[v].push_back(u);
  29.     weight[v].push_back(w);
  30.   }
  31. }
  32.  
  33. int d[MAX_N];
  34. bool scanned[MAX_N];
  35. set<pair<int,int>> Q;
  36.  
  37. void shortest_path(int s, int t)
  38. {
  39.   Q.clear();
  40.   for(int i=0; i<n; i++) {
  41.     d[i] = INFINITY;
  42.     scanned[i] = false;
  43.     Q.insert(make_pair(d[i],i));
  44.   }
  45.   d[s] = 0;
  46.   Q.insert(make_pair(0,s));
  47.  
  48.   while(true) {
  49.     int mind = INFINITY + 1;
  50.     int u = -1;
  51.     /*
  52.     for(int v=0; v<n; v++)
  53.       if((!scanned[v]) && (d[v] < mind)) {
  54.         u = v;
  55.         mind = d[v];
  56.       }
  57.     */
  58.  
  59.     pair<int,int> smallest = *(Q.begin());
  60.     Q.erase(Q.begin());
  61.  
  62.     u = smallest.second;
  63.     mind = d[u];
  64.     if(scanned[u])
  65.       continue;
  66.    
  67.     if(mind >= INFINITY) {
  68.       break;
  69.     }
  70.  
  71.     if(u==t) {
  72.       cout << d[u] << endl;
  73.       return;
  74.     }
  75.     scanned[u] = true;
  76.     for(int i=0; i<adj[u].size(); i++) {
  77.       int v = adj[u][i];
  78.       int w = weight[u][i];
  79.  
  80.       if(d[u] + w < d[v]) {
  81.         d[v] = d[u] + w;
  82.         Q.insert(make_pair(d[v],v));
  83.       }
  84.     }
  85.   }
  86.   cout << "unreachable\n";
  87. }
  88.  
  89. main()
  90. {
  91.   cin >> numtest;
  92.   for(int i=0; i<numtest; i++) {
  93.     read_input();
  94.     cout << "Case #" << (i+1) << ": ";
  95.     shortest_path(s,t);
  96.   }
  97. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement