Today i was solving cses graph problems Shortest Routes I LINK and i am using Dijkstra’s algorithms and after submitting i am getting wrong answer , please help me to find out the error.
My Code
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define INF 0x3f3f3f3f
#define fastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
ll n, k, m, V, E;
vector<pair<ll,ll>> adj[1000005];
int main(){
cin >> V >> E;
for(ll i = 0; i<E; i++){
ll a, b, c;
cin >> a >> b >> c;
--a;
--b;
adj[a].push_back({b , c});
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>> , greater<pair<ll, ll>> > pq;
vector<ll> dist(V, INF);
pq.push({0, 0}); // distance, source.
dist[0] = 0;
while(!pq.empty()){
ll u = pq.top().second;
pq.pop();
for(auto p : adj[u]){
ll v = p.first;
ll w = p.second;
if(dist[v] > w + dist[u]){
dist[v] = w + dist[u];
pq.push({dist[v], v});
}
}
}
for(ll i = 0; i<V; i++){
cout << dist[i] << " ";
}
return 0;
}
Thankyou in advance
/*
1) Initialize distances of all vertices as infinite.
2) Create an empty priority_queue pq. Every item
of pq is a pair (weight, vertex). Weight (or
distance) is used used as first item of pair
as first item is by default used to compare
two pairs
3) Insert source vertex into pq and make its
distance as 0.
4) While either pq doesn't become empty
a) Extract minimum distance vertex from pq.
Let the extracted vertex be u.
b) Loop through all adjacent of u and do
following for every vertex v.
// If there is a shorter path to v
// through u.
If dist[v] > dist[u] + weight(u, v)
(i) Update distance of v, i.e., do
dist[v] = dist[u] + weight(u, v)
(ii) Insert v into the pq (Even if v is
already there)
5) Print distance array dist[] to print all shortest
paths.
*/
// create adjacency list of pair
// adj[u].pb({v,cost}) from u to v cost is cost
void Dijikistra(vector<pii>adj[] , lli v , lli source){
lli dist[v+1];
for(lli i=1;i<=v;i++)
dist[i] = INF;
dist[source] = 0;
// min priority queue of pair
// where pair is < (cost from u to v) , node >
priority_queue<pii , vector<pii> , greater<pii> > pq;
pq.push(make_pair(0,source)); // from source to source cost is 0
while(!pq.empty()){
pii mpair = pq.top();
lli u = mpair.S;
pq.pop();
if(dist[u]<mpair.F)
continue;
for(auto xt : adj[u]){
lli v = xt.F;
lli weight = xt.S;
if(dist[v] > (dist[u] + weight) )
{
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v] , v));
}
}
}
for(lli i=1;i<=v;i++)
cout<<dist[i]<<" ";
}
int main(){
fastio
lli t=1;
//cin>>t;
chandan2();
while(t--) {
lli v,e;
cin>>v>>e;
vector<pii>adj[v+1];
loop(i,e){
lli x,y,cost;
cin>>x>>y>>cost;
adj[x].pb(make_pair(y,cost));
}
Dijikistra(adj,v,1);
}
return 0;
}
1 Like
ThankYou bhaiya for your help.
But can could you see my code and tell me where i am lacking and writing the wrong code
U can see the test case on which it gave WA.