fork(1) download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <cstring>
  5.  
  6. using namespace std;
  7.  
  8. typedef pair<long long, int> lli;
  9.  
  10. const long long oo = ((1 << 30)-1)*2-1;
  11. const int max_n = 5000+1;
  12.  
  13. int n, m;
  14. long long min_d, dist = 0, f[max_n];
  15. vector<lli> adj[max_n];
  16.  
  17. inline void load_map()
  18. {
  19.     cin >> n >> m;
  20.     int type, u, v, w;
  21.     while (m--)
  22.     {
  23.         cin >> type >> u >> v >> w;
  24.         adj[u].push_back(lli(w, v));
  25.         if (type==2) adj[v].push_back(lli(w, u));
  26.     }
  27. }
  28.  
  29. inline void dijkstra()
  30. {
  31.     vector<lli>::iterator it;
  32.     long long cuv, du, d[max_n];
  33.     int u, v;
  34.     priority_queue<lli, vector<lli>, greater<lli> > heap;
  35.     for (u=1; u <= n; u++) d[u] = +oo;
  36.     memset(f, 0, sizeof(f));
  37.     d[1] = 0; f[1] = 1;
  38.     heap.push(lli(0, 1));
  39.     while (heap.size())
  40.     {
  41.         du = heap.top().first; u = heap.top().second;
  42.         heap.pop();
  43.         if (du != d[u]) continue;
  44.         if (u == n) break;
  45.         for (it=adj[u].begin(); it != adj[u].end(); it++)
  46.         {
  47.             cuv = it->first; v = it->second;
  48.             if (d[v]==d[u]+cuv) f[v] += f[u];
  49.             if (d[v] > d[u]+cuv)
  50.             {
  51.                 d[v] = d[u]+cuv;
  52.                 f[v] = f[u];
  53.                 heap.push(lli(d[v], v));
  54.             }
  55.         }
  56.     }
  57.     min_d = d[n];
  58. }
  59.  
  60. main()
  61. {
  62.     load_map();
  63.     dijkstra();
  64.     cout << min_d << " " << f[n];
  65. }
Success #stdin #stdout 0s 4512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/ELwAFE
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!