Проблемы с запуском алгоритма Дейкстры - PullRequest
Новая
       28

Проблемы с запуском алгоритма Дейкстры

0 голосов
/ 12 мая 2019

Я применяю алгоритм Дейкстры для решения конкретной задачи.

Моя проблема в том, что когда я уменьшаю значения v--; u--;, программа автоматически завершается.Я не знаю, есть ли переполнение или что-то конкретное.

Когда я удаляю строки, где значения v--; or--;, программа работает хорошо, но не выдает мне правильные ответы, потому что мне нужно уменьшить обазначения.

Если вы можете помочь мне найти проблему, я буду благодарен 

#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;
}

Контрольный пример 5 3 a 0 4 8 b 0 4 8 c 2 3 1 4 0 1 0 4 2 4 1 4

Это мой результат, когда я удаляю строки, где v--;u -; Unreacheble 8 8 8

Ожидаемый результат Unreachable 8 13 Unreachable

1 Ответ

0 голосов
/ 12 мая 2019

Внимательно посмотрите на то, что происходит в цикле while(m--) {...}.Когда вы читаете строку a 0 4 8 со входа, v устанавливается в ноль.Затем в цикле while вы уменьшаете значение v, выполняя v--, устанавливая v в отрицательное значение.После этого вы пытаетесь получить доступ к g[v] = g[-1] в этой строке: g[v].push_back(make_pair(u , w));, что вызывает ошибку во время выполнения, потому что вы не можете получить доступ к элементам вектора, используя отрицательный индекс.

...