// this code doesnt work unless you comment the lines 71-73 part...
// proof:
/*
input
5 5
1 2 1
2 3 1
3 4 1
4 5 1
1 5 1000
1
then input
5 5
1 5 1000
1 2 1
2 3 1
3 4 1
4 5 1
1
if you un-comment the lines, both output differently.
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) (v).begin(), (v).end()
#define endl '\n'
#define MOD 1000000007
ll mod(ll a) {
return (a%MOD + MOD)%MOD;
}
ll binpow(ll x, ll n) {
if (n == 0) {
return 1;
}
if (x == 0) {
return 0;
}
if (n%2 == 0) {
ll temp = binpow(x,n/2);
return mod(temp*temp);
}
return mod(mod(x)*binpow(x,n-1));
}
void print(bool& ans) { cout << (ans ? "YES" : "NO") << endl; }
// now we have weights(positive). Had weights were negative, we couldnot have used it.
#define f first
#define s second
vector<vector<pair<ll,ll>>> adj;
vector<ll> vis, dis;
void sssp(int src) {
dis[src] = 0;
queue<ll> q;
q.push(src);
while (!q.empty()) {
int node = q.front();
q.pop();
// if (vis[node]) { // the code works when you comment this part, because now for every time a node is pushed, it checks for distance.
// continue;
// }
vis[node] = 1;
for (auto &x:adj[node]) {
if (dis[x.f] > dis[node] + x.s) {
dis[x.f] = dis[node] + x.s;
q.push(x.f);
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
adj = vector<vector<pair<ll,ll>>> (n+1);
vis = vector<ll> (n+1,0);
dis = vector<ll> (n+1,1e9);
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
int src;
cin >> src;
sssp(src);
for (int i = 1; i <= n; i++) {
cout << i << ": " << dis[i] << endl;
}
return 0;
}
WHAT IS THE TIME COMPLEXITY OF THIS APPROACH? IS THIS BETTER THAN OTHER SSSP ALGORITHMS?
You Can Use dijkstra algorithm for SSSP which Compelxity batter then Your code.
I understand, but what is the complexity of this code?
Dijkstra Algorithm, Time Complexity : O(Elog(V)) and Your code is almost O(EV) time Complexity.
It looks like you're trying to apply BFS-like traversal to a graph with weighted edges, which just doesn't work. You keep pushing nodes to the queue based on their proximity to the starting node, but with no respect to actual distances.
Just use Dijkstra's algorithm with something like a
std::priority_queue
.it is working if i am not marking them as visited (see commented line)