Борьба с вычислением кратчайшего пути в графе со специальными весами ребер

Я работал над проблемой, когда мне нужно найти кратчайший путь в графе, учитывая два типа весов ребер: нормальный и специальный. Проверьте проблему здесь.

Я составил список смежности и использовал алгоритм Дейкстры, чтобы найти кратчайшее расстояние. Однако у меня возникают проблемы с получением правильных результатов для некоторых тестовых случаев.

Вот краткий обзор моего подхода:

1. Представление графа: я использовал список смежности для хранения ребер. Каждое ребро имеет нормальный и специальный вес.
2. Алгоритм Дейкстры: я реализовал алгоритм Дейкстры, используя очередь с приоритетом минимальной кучи. Я поддерживаю массив расстояний для хранения кратчайших расстояний, учитывая как обычные, так и специальные веса.

Несмотря на такой подход, я сталкиваюсь с проблемами, из-за которых расстояния не всегда рассчитываются правильно, а некоторые тестовые примеры завершаются неудачно. В частности, я считаю, что проблема заключается в том, как я обращаюсь со специальными весами в процессе релаксации кромок.

#include <bits/stdc++.h> 
using namespace std;

typedef pair<int, int> Pair;

struct Edge {
 int v;
 int normal;
 int special;
};

int findShortestDistance(int numberOfVertices, vector<vector<int>> &adj, int src, int dst) {
 vector<vector<Edge>> adjacencyList(numberOfVertices + 1);

 // Building the adjacency list
 for (int i = 0; i < adj.size(); i++) {
     adjacencyList[adj[i][0]].push_back({adj[i][1], adj[i][2], adj[i][3]});
 }

 // Min heap priority queue
 priority_queue<Pair, vector<Pair>, greater<Pair>> minHeap;
 vector<vector<int>> distanceFromSource(numberOfVertices + 1, vector<int>(2, INT_MAX));

 minHeap.push({0, src});
 distanceFromSource[src][0] = 0;

 while (!minHeap.empty()) {
     auto currentPair = minHeap.top();
     minHeap.pop();

     int currentNode = currentPair.second;
     int currentDistance = currentPair.first;

     // Exploring neighbors
     for (auto neighbor : adjacencyList[currentNode]) {
         int neighborNode = neighbor.v;
         int edgeWeight = neighbor.normal;
         int specialWeight = neighbor.special;

         // Relaxing the edge with normal weight
         if (distanceFromSource[neighborNode][0] > currentDistance + edgeWeight) {
             distanceFromSource[neighborNode][0] = currentDistance + edgeWeight;
             minHeap.push({distanceFromSource[neighborNode][0], neighborNode});
         }

         // Relaxing the edge with special weight
         if (distanceFromSource[neighborNode][1] > currentDistance + specialWeight) {
             distanceFromSource[neighborNode][1] = currentDistance + specialWeight;
             // minHeap.push({distanceFromSource[neighborNode][1], neighborNode});
         }
     }
 }

 return min(distanceFromSource[dst][0], distanceFromSource[dst][1]);
}