fork download
  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
stdin
Standard input is empty
stdout
0 0