fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 1e5 + 5; 
  12. const int MOD = 1e9 + 7;  
  13.  
  14. template<typename T>
  15. void maximize(T& a, const T& b) {
  16. 	if (a < b) a = b;  
  17. }
  18.  
  19. template<typename T>
  20. void minimize(T& a, const T& b) {
  21. 	if (b < a) a = b; 
  22. }
  23.  
  24. void add(int& a, int b) {
  25. 	a += b; 
  26. 	if (a >= MOD) a -= MOD; 
  27. }
  28.  
  29. int n, m;  
  30. vector<ii> adj[N]; 
  31.  
  32. struct Node {
  33. 	int u; ll d;  
  34. 	bool operator<(const Node& other) const {
  35. 		return d > other.d; 
  36. 	}
  37. }; 
  38.  
  39. ll dist[N]; // dist[u] = Đường đi ngắn nhất từ s đến u
  40. int cnt[N]; // cnt[u] = Số đường đi ngắn nhất từ s đến u
  41. int mx[N]; // mx[u] = Số đỉnh trên đường đi ngắn nhất từ s đến u mà đi qua nhiều đỉnh nhất
  42. int mn[N]; // mn[u] = Số đỉnh trên đường đi ngắn nhất từ s đến u mà đi qua ít đỉnh nhất
  43.  
  44. void dijkstra(int s) {
  45. 	for (int u = 1; u <= n; u++) {
  46. 		dist[u] = LINF; 
  47. 		cnt[u] = 0;  
  48. 		mx[u] = 0; 
  49. 		mn[u] = INF; 
  50. 	}
  51.  
  52. 	priority_queue<Node> pq;  
  53. 	dist[s] = 0;  
  54. 	cnt[s] = 1;   
  55. 	mx[s] = mn[s] = 0;  
  56. 	pq.push({s, dist[s]});  
  57.  
  58. 	while (!pq.empty()) {
  59. 		Node front = pq.top(); pq.pop();  
  60. 		int u = front.u; ll d = front.d;  
  61.  
  62. 		if (d > dist[u]) continue;  
  63.  
  64. 		for (ii v : adj[u]) {
  65. 			if (dist[u] + v.second < dist[v.first]) {
  66. 				dist[v.first] = dist[u] + v.second;  
  67. 				cnt[v.first] = cnt[u];                             
  68. 				mx[v.first] = mx[u] + 1;  
  69. 				mn[v.first] = mn[u] + 1; 
  70. 				pq.push({v.first, dist[v.first]});  
  71. 			}
  72. 			else if (dist[u] + v.second == dist[v.first]) {
  73. 				add(cnt[v.first], cnt[u]);  
  74. 				maximize(mx[v.first], mx[u] + 1); 
  75. 				minimize(mn[v.first], mn[u] + 1);  
  76. 			}
  77. 		}
  78. 	}
  79. }
  80.  
  81. int main() {
  82. 	ios::sync_with_stdio(false); 
  83. 	cin.tie(nullptr); 	
  84. 	cin >> n >> m; 
  85.  
  86. 	for (int i = 0; i < m; i++) {
  87. 		int u, v, w; 
  88. 		cin >> u >> v >> w; 
  89. 		adj[u].push_back({v, w}); 
  90. 	}
  91.  
  92. 	dijkstra(1); 
  93.  
  94. 	cout << dist[n] << ' ' << cnt[n] << ' ' << mn[n] << ' ' << mx[n] << '\n'; 
  95. }
Success #stdin #stdout 0.01s 6320KB
comments (?)
stdin
copy 
4 5
1 4 5
1 2 4
2 4 5
1 3 2
3 4 3
stdout
copy 
5 2 1 2
https://ideone.com/ALnn0r
language:
C++14 (gcc 8.3)
created:
282 days 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!