fork(1) download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <unordered_set>
  4. #include <vector>
  5. #include <string>
  6. #include <map>
  7. #include <algorithm>
  8.  
  9. using namespace std;
  10.  
  11. #define fst first
  12. #define snd second
  13.  
  14. const int INF = 99999999;
  15. struct graph {
  16.   int n;
  17.   struct edge { int src, dst, weight; };
  18.   vector<vector<edge>> adj, rdj;
  19.   graph(int n) : n(n), adj(n), rdj(n) { }
  20.   void add_edge(int u, int v, int w) {
  21.     adj[u].push_back({u, v, w});
  22.     rdj[v].push_back({v, u, w});
  23.   }
  24.  
  25.   // bidirectional dijkstra
  26.   int shortest_path(int s, int t) {
  27.     if (s == t) return 0;
  28.     vector<int> ds(n, INF), dt(n, INF);
  29.     typedef pair<int, int> node;
  30.     priority_queue<node, vector<node>, greater<node>> Qs, Qt;
  31.     Qs.push({ds[s] = 0, s});
  32.     Qt.push({dt[t] = 0, t});
  33.     int mu = INF;
  34.     while (!Qs.empty() && !Qt.empty()) {
  35.       if (Qs.top().fst + Qt.top().fst >= mu) break;
  36.       if (Qs.top().fst <= Qt.top().fst) {
  37.         node x = Qs.top(); Qs.pop();
  38.         if (ds[x.snd] > x.fst) continue;
  39.         for (edge &e: adj[x.snd]) {
  40.           if (ds[e.src] + e.weight < ds[e.dst]) {
  41.             mu = min(mu, ds[e.src] + e.weight + dt[e.dst]);
  42.             ds[e.dst] = ds[e.src] + e.weight;
  43.             Qs.push({ds[e.dst], e.dst});
  44.           }
  45.         }
  46.       } else {
  47.         node x = Qt.top(); Qt.pop();
  48.         if (dt[x.snd] > x.fst) continue;
  49.         for (edge &e: rdj[x.snd]) {
  50.           if (dt[e.src] + e.weight < dt[e.dst]) {
  51.             mu = min(mu, dt[e.src] + e.weight + ds[e.dst]);
  52.             dt[e.dst] = dt[e.src] + e.weight;
  53.             Qt.push({dt[e.dst], e.dst});
  54.           }
  55.         }
  56.       }
  57.     }
  58.     return mu;
  59.   }
  60.  
  61.   // single directional dijkstra
  62.   int shortest_path2(int s, int t) {
  63.     vector<int> dist(n, INF);
  64.     typedef pair<int, int> node;
  65.     priority_queue<node, vector<node>, greater<node>> Q;
  66.     Q.push({dist[s] = 0, s});
  67.     while (!Q.empty()) {
  68.       node x = Q.top(); Q.pop();
  69.       if (x.snd == t) break;
  70.       if (dist[x.snd] > x.fst) continue;
  71.       for (edge &e: adj[x.snd]) {
  72.         if (dist[e.src] + e.weight < dist[e.dst]) {
  73.           dist[e.dst] = dist[e.src] + e.weight;
  74.           Q.push({dist[e.dst], e.dst});
  75.         }
  76.       }
  77.     }
  78.     return dist[t];
  79.   }
  80. };
  81.  
  82.  
  83. // === tick a time ===
  84. #include <ctime>
  85. double tick() {
  86.   static clock_t oldtick;
  87.   clock_t newtick = clock();
  88.   double diff = 1.0*(newtick - oldtick) / CLOCKS_PER_SEC;
  89.   oldtick = newtick;
  90.   return diff;
  91. }
  92. int test() {
  93.   int n = 2000; 
  94.   graph g(n);
  95.   for (int u = 0; u < n; ++u) {
  96.     int d = 1 + rand() % 30;
  97.     unordered_set<int> N;
  98.     while (N.size() < d) {
  99.       int v = rand() % n;
  100.       if (u != v) N.insert(v);
  101.     }
  102.     for (auto v: N) {
  103.       int w = 1 + rand() % 10;
  104.       g.add_edge(u, v, w);
  105.     }
  106.   }
  107.   double t1 = 0, t2 = 0;
  108.   for (int u = 0; u < n; ++u) {
  109.     int v = rand() % n;
  110.     tick();
  111.     int a = g.shortest_path(u, v);
  112.     t1 += tick();
  113.     int b = g.shortest_path2(u, v);
  114.     t2 += tick();
  115.     if (a != b) {
  116.       cout << u << " -> " << v << ": " << a << " / " << b << endl;
  117.       return false;
  118.     }
  119.   }
  120.   cout << t1 << " " << t2 << endl;
  121.   cout << "bidirectional dijkstra is " << t2/t1 << " times faster" << endl;
  122.   return true;
  123. }
  124.  
  125. // verify: SPOJ SHPATH
  126. void solve() {
  127.   int n; 
  128.   scanf("%d", &n);
  129.   graph g(n);
  130.   map<string, int> id;
  131.   for (int u = 0; u < n; ++u) {
  132.     char name[1024];
  133.     scanf("%s", name);
  134.     id[name] = u;
  135.     int k;
  136.     scanf("%d", &k);
  137.     for (int j = 0; j < k; ++j) {
  138.       int v, d;
  139.       scanf("%d %d", &v, &d);
  140.       g.add_edge(u, v-1, d);
  141.     }
  142.   }
  143.   int k;
  144.   scanf("%d", &k);
  145.   for (int i = 0; i < k; ++i) {
  146.     char s[1024], t[1024];
  147.     scanf("%s %s", s, t);
  148.     printf("%d\n", g.shortest_path(id[s], id[t]));
  149.   }
  150. }
  151.  
  152. int main() {
  153.   test();
  154.   return 0;
  155.  
  156.   // verify: SPOJ SHPATH
  157.   int ncase; scanf("%d", &ncase);
  158.   for (int icase = 0; icase < ncase; ++icase) solve();
  159. }
  160.  
Success #stdin #stdout 1.02s 3424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.120543 0.889874
bidirectional dijkstra is 7.38221 times faster
https://ideone.com/J9awus
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!