Can somebody tell why this code is giving runtime error?
Thanks in advance
#include
#include
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000000000
#define test ll t; t=1; while(t–)
typedef long long int ll;
void dijakstra(vector<vector<pair<ll,ll>>>adj,vectord,vectorp,ll s,ll n){
d.assign(n,mod);
p.assign(n,-1);
set<pair<ll,ll>>q;
q.insert({0,s});
d[s]=0;
while(!q.empty()){
ll v,to,len;
v=q.begin()->second;
q.erase(q.begin());
for(auto i:adj[v]) {
to=i.first;
len=i.second;
if(d[to]>d[v]+len){
d[to]=d[v]+len;
p[to]=v;
q.insert({d[to],to});
}
}
}
}
int main() {
FIO;
test{
vector<vector<pair<ll,ll>>> adj;
ll n,m,i,l,r,w,s;
cin>>n>>m;
cin>>s;
for(i=0;i<m;i++){
cin>>l>>r>>w;
adj[l].push_back(make_pair(r,w));
adj[r].push_back(make_pair(l,w));
}
vectord;
vectorp;
dijakstra(adj,d,p,0,n);
for(i=0;i<n;i++){
cout<<i<<" "<<d[i]<<endl;
}
}
return 0;
}
Please format your code - the forum software has mangled it and it won’t compile!
Also - what test input is causing the runtime error?
#include <iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000000000
#define test ll t; t=1; while(t--)
typedef long long int ll;
void dijakstra(vector<vector<pair<ll,ll>>>adj,vector<ll>d,vector<ll>p,ll s,ll n){
d.assign(n,mod);
p.assign(n,-1);
set<pair<ll,ll>>q;
q.insert({0,s});
d[s]=0;
while(!q.empty()){
ll v,to,len;
v=q.begin()->second;
q.erase(q.begin());
for(auto i:adj[v]) {
to=i.first;
len=i.second;
if(d[to]>d[v]+len){
d[to]=d[v]+len;
p[to]=v;
q.insert({d[to],to});
}
}
}
}
int main() {
FIO;
test{
vector<vector<pair<ll,ll>>> adj;
ll n,m,i,l,r,w,s;
cin>>n>>m;
cin>>s;
for(i=0;i<m;i++){
cin>>l>>r>>w;
adj[l].push_back(make_pair(r,w));
adj[r].push_back(make_pair(l,w));
}
vector<ll>d;
vector<ll>p;
dijakstra(adj,d,p,0,n);
for(i=0;i<n;i++){
cout<<i<<" "<<d[i]<<endl;
}
}
return 0;
}
Test case:
9 14
0
0 1 4
0 7 8
1 2 8
1 7 11
2 3 7
2 8 2
2 5 4
3 4 9
3 5 14
4 5 10
5 6 2
6 7 1
6 8 6
7 8 7
First error, line 39:
adj[l].push_back(make_pair(r,w));
^ ^
adj
is still empty, so adj[l]
is an out-of-bounds access.
As ssjgz pointed out you need to use
vector<vector<int>> adj(n);
To initialise with n vectors.
But i like using
vector<int> adj[n];
Bro do u have codes for basic algos of graph theory like flyod warshall,Belleman ford etc
Can we add a large constant to the edges to perform dijikstra instead of belmanford?
Then you even need to keep track of no of edges you have processed as you need to subtract that constant back from each edge
Thanks a lot.
No @dean_student that is not true. Adding a large constant incentivises shorter length rather than distance. For example consider the graph from 1 to 4.
Over here if you add a large constant, it will disproportionally affect the shorter route, by 3 times.
A constant of 3 is enough to change the answer to 6, and the shorter path will have a distance of 7. Even after subtracting 3 after the search we’ll get 3. Which is incorrect, as the answer is actually -2.
Got it bro , thanks
Bro can’t it be done once we keep track of no of edges like in shortest path we get 6 which is 6-3 and 7 in another path which is actually 7-3*3=-2
But it will be diffficult to maintain set
Then it loses it’s time conplexity.
This post was flagged by the community and is temporarily hidden.