I have been implementing the dijkstra algorithm for a particular problem to solve.

My problem is when I decrease the values v--; u--; the program automatically culminates. I do not know if there is any overflow or something in particular.

When I delete the lines where the values v--; or--; the program works well but does not throw me the correct answers, because I need to decrease both values.

If you can help me find the problem, I'll be grateful

#include <bits/stdc++.h>

using namespace std;


#define endl '\n'
#define forn(i , a , b) for(int i=(a);i<(b);i++)


int const N = 1001;
int const M = numeric_limits<int>::max();
bool visited[N];
vector<int> cost(N);
vector<vector<pair<int, int>>> g;
priority_queue<pair<int, int>> q;


void dijkstra(int src) {
  cost[src] = 0;
  q.push(make_pair(0, src));
  while(!q.empty()){
    int v = q.top().second;
    int c = -q.top().first;
    q.pop();
    if(visited[v]) continue;
      visited[v] = true;
      forn(i , 0 , (int)g[v].size()){
        if(g[v][i].second + c < cost[g[v][i].first]) {
          cost[g[v][i].first] = g[v][i].second + c;
          q.push(make_pair(-(g[v][i].second + c), g[v][i].first));
         }
      }
   }
}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;  

#ifdef LOCAL_DEFINE
  freopen("input.txt" , "rt" , stdin);
#endif

   int n; cin >> n;
   int m; cin >> m;
   g.resize(n);
   while(!q.empty()) q.pop(); 
   forn(i , 0 , n) cost[i] = M;
   memset(visited , false , sizeof visited);
   while(m--){
     string s; cin >> s;
     int v; cin >> v;
     int u; cin >> u;
     int w; cin >> w;
     v--; u--;
     g[v].push_back(make_pair(u , w));
   }
   int t; cin >> t;
   while(t--){
     int v; cin >> v;
     int u; cin >> u;
     v--; u--;
     dijkstra(v);
     if(cost[u] == M) cout << "Unreachable" << endl;
     else cout << cost[u] << endl;
   }

#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif  
  return 0;
}

Test Case 5 3 a 0 4 8 b 0 4 8 c 2 3 1 4 0 1 0 4 2 4 1 4

This is my result, when I delete the lines where v--; u--; Unreacheble 8 8 8

Expected output Unreachable 8 13 Unreachable

1 Answers

0
kindanoob On

Look carefully at what is happening in the while(m--) {...} loop. When you are reading the line a 0 4 8 from input, v is set to zero. Then, in the while loop you decrease the value of v by doing v-- setting v to negative one. After this you try to access g[v] = g[-1] in this line: g[v].push_back(make_pair(u , w)); which causes a runtime error, because you cannot access elements of vector using negative index.