Struggling with Shortest Path Calculation in Graph with Special Edge Weights

I've been working on a problem where I need to find the shortest path in a graph considering two types of edge weights: normal and special. Check Problem Here.

I have constructed an adjacency list and used Dijkstra's algorithm to find the shortest distance. However, I'm facing issues getting correct results for some test cases.

Here's a brief overview of my approach:

1. Graph Representation: I used an adjacency list to store edges. Each edge has a normal weight and a special weight.
2. Dijkstra's Algorithm: I implemented Dijkstra's algorithm using a min-heap priority queue. I maintain a distance array to store the shortest distances considering both normal and special weights.

Despite this approach, I'm encountering issues where the distances aren't always calculated correctly, and some test cases fail. Specifically, I believe the problem lies in how I handle the special weights during the edge relaxation process.

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

You are using currentDistance to calculate the best paths for the next node without considering if that path already included a special edge.

Without changing your code too much, you can directly get the distances from the distanceFromSource vector instead.

There is only one way to create a path to the neighbor without using a special edge: use the shortest path found so far to the current node that does not use a special edge and connect it the neighbor via a normal edge.

For a path that uses a special edge, you can either use the shortest path to the current node that already uses a special edge and take the normal edge to the neighbor, or use the shorest path to the current that does not use a special edge and then take the special edge to the neighbor.

With these edits, your solution will pass:

std::vector<std::vector<int>> distanceFromSource(numberOfVertices + 1, std::vector<int>(2, 1e9));
// don't use INT_MAX as it results in overflow later

// inside the loop:
if (distanceFromSource[neighborNode][0] > distanceFromSource[currentNode][0] + edgeWeight) {
    minHeap.push({distanceFromSource[neighborNode][0] = distanceFromSource[currentNode][0] + edgeWeight, neighborNode});
}
int bestWithSpecial = std::min(distanceFromSource[currentNode][1] + edgeWeight, distanceFromSource[currentNode][0] + specialWeight);
if (distanceFromSource[neighborNode][1] > bestWithSpecial) {
    minHeap.push({
        distanceFromSource[neighborNode][1] = bestWithSpecial,
        neighborNode
    });
}

Note that this can be optimized more to avoid adding unnecessary nodes to the priority queue.