#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
vector<int> dijkstra(int n, vector<vector<pair<int, int>>>& adj) {
vector<int> dist(n, INT_MAX);
dist[0] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0}); // {distance, node}
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (auto& edge : adj[u]) {
int v = edge.first;
int time = edge.second;
if (dist[u] + time < dist[v]) {
dist[v] = dist[u] + time;
pq.push({dist[v], v});
}
}
}
return dist;
}
int countWays(int n, vector<vector<pair<int, int>>>& adj, vector<int>& dist) {
vector<long long> dp(n, 0);
dp[0] = 1;
vector<vector<int>> dag(n);
for (int u = 0; u < n; ++u) {
for (auto& edge : adj[u]) {
int v = edge.first;
int time = edge.second;
if (dist[u] + time == dist[v]) {
dag[u].push_back(v);
}
}
}
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : dag[u]) {
dp[v] = (dp[v] + dp[u]) % MOD;
q.push(v);
}
}
return dp[n - 1];
}
int countPaths(int n, vector<vector<int>>& roads) {
vector<vector<pair<int, int>>> adj(n);
for (auto& road : roads) {
int u = road[0];
int v = road[1];
int time = road[2];
adj[u].push_back({v, time});
adj[v].push_back({u, time});
}
vector<int> dist = dijkstra(n, adj);
return countWays(n, adj, dist);
}
int main() {
int n = 7;
vector<vector<int>> roads = {
{0, 6, 7}, {0, 1, 2}, {1, 2, 3}, {1, 3, 3}, {6, 3, 3},
{3, 5, 1}, {6, 5, 1}, {2, 5, 1}, {0, 4, 5}, {4, 6, 2}
};
cout << countPaths(n, roads) << endl; // Output: 4
return 0;
}
.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int countPaths(int n, vector<vector<int>>& roads) {
vector<vector<pair<int, int>>> adj(n);
// Build adjacency list
for (auto& road : roads) {
int u = road[0];
int v = road[1];
int time = road[2];
adj[u].push_back({v, time});
adj[v].push_back({u, time});
}
// Dijkstra's algorithm with a priority queue
vector<int> dist(n, INT_MAX);
vector<int> ways(n, 0);
dist[0] = 0;
ways[0] = 1;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0}); // {distance, node}
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (auto& edge : adj[u]) {
int v = edge.first;
int time = edge.second;
if (dist[u] + time < dist[v]) {
dist[v] = dist[u] + time;
ways[v] = ways[u]; // reset ways count for v
pq.push({dist[v], v});
} else if (dist[u] + time == dist[v]) {
ways[v] = (ways[v] + ways[u]) % MOD; // increment ways count for v
}
}
}
return ways[n - 1];
}
int main() {
int n = 7;
vector<vector<int>> roads = {
{0, 6, 7}, {0, 1, 2}, {1, 2, 3}, {1, 3, 3}, {6, 3, 3},
{3, 5, 1}, {6, 5, 1}, {2, 5, 1}, {0, 4, 5}, {4, 6, 2}
};
cout << countPaths(n, roads) << endl; // Output the number of ways
return 0;
}
Which code is better in your opinion, which approach should i learn ?
I think it's mostly about your style choice. If I were to choose, I would choose the 2nd option simply because I feel like having an extra method just for the Dijkstra isn't necessary.
Agreed.
123gjweq2
If Dijkstra will be not only one algorithm in problem I would choose first option in other cases i would choose second. But if you wanna keep your code debugable always use first option.
neither