Я пытался решить проблему spoj dijkstra
это в основном реализация алгоритма Дейкстры. Я пытался реализовать алгоритм, используя набор STL, но я не получаю правильный вывод.
Когда я пытался отладить код i в соответствии с первым тестовым примером, приведенным в ссылке выше, я начинаю с первой вершины, вставляя в набор, а затем я вставляю дочернюю. Но первая вершина соединяется с 2 и 3 и они должны быть вставлены в набор соответственно и цикл внутри дейкстры должен работать 2
раз, но работает 3 раза
Эта проблема может быть связана с векторным вводом (график) или
для цикла внутри дейкстра скорее всего
Поскольку я новичок в STL, мне нужна твоя помощь
#include<vector>
#include<map>
#include<string>
#include<iostream>
#include<cstring>
#include<set>
#define Size 10000
#define MAX 100000
#define INF 1000000000
using namespace std;
vector <pair<int, int>> v[Size + 1];
map<string, int> mep;
int dist[Size];
bool visited[Size];
void dijkstra(int n) {
for (int i = 0; i < 100; i++) { //doing for less than 100 to check for small test cases
dist[i]=INF;
visited[i] = false;
}
dist[n] = 0;
cout << endl;
multiset <pair<int, int >>s;
s.insert({ 0,n });
while (!s.empty()) {
/*cout << endl;
cout << "printing my set or queue" << endl;
multiset<pair<int, int>>::iterator iter;
for (iter = s.begin(); iter != s.end(); iter++) {
cout << " first value of set " << (*iter).first;
cout << " second value of set " << (*iter).second;
cout << endl;
}
cout << endl;*/
pair<int, int> p = *s.begin();
s.erase(s.begin());
int x = p.second;
int wei = p.first;
if (visited[x])
continue;
visited[x] = true;
for (int i = 0; i < v[x].size(); i++) {
int e = v[x][i].first;
int w = v[x][i].second;
if (dist[x] + w < dist[e]) {
dist[e] = dist[x] + w;
/*cout << "parent vertex or x is " << x << " dist[x]=" << dist[x] << endl;
cout << "child processing e is " << e << " dist[e]="<<dist[e] << endl;
cout << "weight or distance of child connected e is =" << w << endl;*/
s.insert({ dist[e],w });
}
}
}
}
int main() {
//dist[0]=1000000000000;
//cout<<dist[0];
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
string str;
cin >> str;
mep[str] = i;
int cities;
cin >> cities;
for (int i = 0; i < cities; i++) {
int city_id;
int city_wei;
cin >> city_id;
cin >> city_wei;
pair <int, int> p;
p.first = city_id;
p.second = city_wei;
v[i].push_back(p);
}
}
int query;
cin >> query;
for (int i = 0; i < query; i++) {
string source;
string dest;
cin >> source;
cin >> dest;
int source_id = mep[source];
int dest_id = mep[dest];
dijkstra(source_id);
cout << dist[dest_id] << endl;
}
}
}