SPFA Shortest Path Algorithm

The Shortest Path Faster Algorithm (SPFA) is an optimization of the Bellman-Ford algorithm that uses a queue to process vertices and provides efficient shortest path computation in graphs with negative edge weights.

Standard SPFA Implementation

#define MAX_VERTICES 400002
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Edge {
    int destination;
    int weight;
};

int vertexCount, edgeCount;
vector<Edge> graph[MAX_VERTICES];
int distanceArray[MAX_VERTICES];
bool inQueue[MAX_VERTICES];
queue<int> vertexQueue;

void shortestPathFasterAlgorithm(int source) {
    int current, neighbor;
    
    // Initialize distances to infinity
    for (int i = 1; i <= vertexCount; i++) {
        distanceArray[i] = INT_MAX;
    }
    distanceArray[source] = 0;
    
    vertexQueue.push(source);
    inQueue[source] = true;
    
    // Process vertices in queue
    while (!vertexQueue.empty()) {
        current = vertexQueue.front();
        vertexQueue.pop();
        inQueue[current] = false;
        
        // Relax all outgoing edges
        for (int i = 0; i < graph[current].size(); i++) {
            neighbor = graph[current][i].destination;
            
            if (distanceArray[neighbor] > distanceArray[current] + graph[current][i].weight) {
                distanceArray[neighbor] = distanceArray[current] + graph[current][i].weight;
                
                if (!inQueue[neighbor]) {
                    vertexQueue.push(neighbor);
                    inQueue[neighbor] = true;
                }
            }
        }
    }
}

int main() {
    int u, v, type, time;
    
    cin >> vertexCount >> edgeCount;
    
    for (int i = 1; i <= edgeCount; i++) {
        cin >> u >> v >> type >> time;
        graph[u].push_back({v, time});
    }
    
    shortestPathFasterAlgorithm(1);
    
    // Output distances from vertex 2 to n
    for (int i = 2; i <= vertexCount; i++) {
        if (distanceArray[i] == INT_MAX) {
            cout << "-1 ";
        } else {
            cout << distanceArray[i] << ' ';
        }
    }
    return 0;
}

SPFA for Layered Graph Problems

When dealing with layered graph problems where edges can connect different layers or stay within the same layer, we extend the vertex space to accommodate both layers:

#define MAX_VERTICES 400002
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Edge {
    int destination;
    int weight;
};

int vertexCount, edgeCount;
vector<Edge> graph[MAX_VERTICES];
int distanceArray[MAX_VERTICES];
bool inQueue[MAX_VERTICES];
queue<int> vertexQueue;

void shortestPathFasterAlgorithm(int source) {
    int current, neighbor;
    
    // Initialize distances for all vertices across both layers
    for (int i = 1; i <= 2 * vertexCount; i++) {
        distanceArray[i] = INT_MAX;
    }
    distanceArray[source] = 0;
    
    vertexQueue.push(source);
    inQueue[source] = true;
    
    while (!vertexQueue.empty()) {
        current = vertexQueue.front();
        vertexQueue.pop();
        inQueue[current] = false;
        
        for (int i = 0; i < graph[current].size(); i++) {
            neighbor = graph[current][i].destination;
            
            if (distanceArray[neighbor] > distanceArray[current] + graph[current][i].weight) {
                distanceArray[neighbor] = distanceArray[current] + graph[current][i].weight;
                
                if (!inQueue[neighbor]) {
                    vertexQueue.push(neighbor);
                    inQueue[neighbor] = true;
                }
            }
        }
    }
}

int main() {
    int u, v, type, time;
    
    cin >> vertexCount >> edgeCount;
    
    for (int i = 1; i <= edgeCount; i++) {
        cin >> u >> v >> type >> time;
        
        if (type == 1) {
            // Same-layer connections
            graph[u].push_back({v, time});           // Layer 1: u -> v
            graph[u + vertexCount].push_back({v + vertexCount, time});  // Layer 2: (u+n) -> (v+n)
        } else {
            // Cross-layer connections
            graph[u].push_back({v + vertexCount, time});  // Layer 1 to Layer 2: u -> v+n
        }
    }
    
    shortestPathFasterAlgorithm(1);
    
    // Take minimum distance from both layers
    for (int i = 2; i <= vertexCount; i++) {
        int result = min(distanceArray[i], distanceArray[i + vertexCount]);
        if (result == INT_MAX) {
            cout << "-1 ";
        } else {
            cout << result << ' ';
        }
    }
    return 0;
}

Extracting and Sorting Digits

Two common approaches for extracting digits from a string and sorting them in descending order:

Using Priority Queue

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

string input;
priority_queue<int> digitQueue;

int main() {
    cin >> input;
    
    for (char c : input) {
        if (c >= '0' && c <= '9') {
            digitQueue.push(c - '0');
        }
    }
    
    while (!digitQueue.empty()) {
        cout << digitQueue.top();
        digitQueue.pop();
    }
    return 0;
}

Using Counting Sort

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

string input;
int digitCount[10];

int main() {
    cin >> input;
    
    for (char c : input) {
        if (c >= '0' && c <= '9') {
            digitCount[c - '0']++;
        }
    }
    
    for (int d = 9; d >= 0; d--) {
        while (digitCount[d] > 0) {
            cout << d << ' ';
            digitCount[d]--;
        }
    }
    return 0;
}

Matrix Posision Calculation

Given a sequence of values, calculate the position of a specific element in a zigzag matrix:

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

int values[102];
int rowCount, columnCount;

void findPosition() {
    int targetValue, currentIndex = 0;
    int greaterCount = 0, position;
    int targetRow, targetColumn, temp;
    
    cin >> rowCount >> columnCount;
    cin >> values[1];
    targetValue = values[1];
    
    // Count elements greater than target
    for (int i = 2; i <= rowCount * columnCount; i++) {
        cin >> values[i];
        if (values[i] > targetValue) {
            greaterCount++;
        }
    }
    
    position = greaterCount + 1;
    
    // Sort in descending order
    sort(values + 1, values + 1 + rowCount * columnCount, greater<int>());
    
    // Calculate row and column
    if (position % rowCount == 0) {
        targetRow = position / rowCount;
    } else {
        targetRow = position / rowCount + 1;
    }
    
    temp = position - (targetRow - 1) * rowCount;
    
    // Handle zigzag column ordering
    if (targetRow % 2 == 1) {
        targetColumn = temp;
    } else {
        targetColumn = rowCount + 1 - temp;
    }
    
    cout << targetRow << ' ' << targetColumn << endl;
}

int main() {
    findPosition();
    return 0;
}

XOR Subarray Problem

Find the maximum number of non-overlapping subarrays where the XOR equals k using prefix XOR technique:

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

int arraySize, targetXor;
int arrayValues[500001];
int prefixXor[500001];
int lastPosition[500001];

int main() {
    int currentXor, requiredXor;
    int result = 0, lastValidEnd = 0;
    int index;
    
    cin >> arraySize >> targetXor;
    
    for (int i = 1; i <= arraySize; i++) {
        cin >> arrayValues[i];
    }
    
    // Initialize with boundary condition
    memset(lastPosition, -1, sizeof(lastPosition));
    lastPosition[0] = 0;  // Empty prefix has XOR 0
    
    for (index = 1; index <= arraySize; index++) {
        prefixXor[index] = prefixXor[index - 1] ^ arrayValues[index];
        requiredXor = prefixXor[index] ^ targetXor;
        
        // Check if we can extend from last valid position
        if (lastPosition[requiredXor] >= lastValidEnd) {
            result++;
            lastValidEnd = index;
        }
        
        // Record the latest position of this prefix XOR
        lastPosition[prefixXor[index]] = index;
    }
    
    cout << result << endl;
    return 0;
}

C++ Set Container and String Hashing

The std::set container provides O(log n) operations for inserting, deleting, and searching elements while maintaining sorted order:

// Set container operations
set<int> numberSet;

// Insert elements
numberSet.insert(10);
numberSet.insert(8);
numberSet.insert(20);

// Iterate through set
for (auto iterator = numberSet.begin(); iterator != numberSet.end(); iterator++) {
    cout << *iterator << ' ';
}

// Erase element
numberSet.erase(10);

// Get size
cout << numberSet.size() << endl;

// Check existence using count
if (numberSet.count(20) == 1) {
    cout << "found" << endl;
}

// Find element
int searchValue = 15;
auto findResult = numberSet.find(searchValue);
if (findResult != numberSet.end()) {
    cout << "found" << endl;
}

// String set for unique strings
set<string> stringSet;
string input;
int count;

cin >> count;
for (int i = 0; i < count; i++) {
    cin >> input;
    stringSet.insert(input);
}

cout <> stringSet.size();

Tower of Hanoi

The Tower of Hanoi problem demonstrates recursive problem-solving where a larger problem is decomposed into smaller subproblems of the same type:

Classic Three-Peg Solution

// Recursive Hanoi solution for 3 pegs
// Parameters: number of disks, source peg, auxiliary peg, destination peg
void hanoiThreePegs(int diskCount, char source, char auxiliary, char destination) {
    if (diskCount == 1) {
        // Base case: single disk moves directly
        cout << source << " -> " << destination << endl;
        return;
    }
    
    // Move n-1 disks to auxiliary peg
    hanoiThreePegs(diskCount - 1, source, destination, auxiliary);
    
    // Move largest disk to destination
    cout << source << " -> " << destination << endl;
    
    // Move n-1 disks from auxiliary to destination
    hanoiThreePegs(diskCount - 1, auxiliary, source, destination);
}

Four-Peg Optimization

For the four-peg variant (Reve's Puzzle), the optimal strategy divides disks into two groups:

// Optimal 4-peg Hanoi solution
// Split n disks into k and n-k groups
void hanoiFourPegs(int diskCount, int k, char source, char auxiliary1, char auxiliary2, char destination) {
    if (diskCount == 0) return;
    
    if (diskCount == 1) {
        cout << source << " -> " << destination << endl;
        return;
    }
    
    // Step 1: Move top k disks from source to first auxiliary (using all 4 pegs)
    hanoiFourPegs(k, k, source, destination, auxiliary2, auxiliary1);
    
    // Step 2: Move remaining n-k disks from source to destination (using 3 pegs)
    hanoiThreePegs(diskCount - k, source, auxiliary2, destination);
    
    // Step 3: Move k disks from auxiliary to destination (using all 4 pegs)
    hanoiFourPegs(k, k, auxiliary1, source, auxiliary2, destination);
}

Pointer Fundamentals

Pointers enable indirect access and modification of memory locations, supporting complex data structures and memory management:

void pointerExamples() {
    int original = 78;
    
    // Single-level pointer
    int *firstLevel = &original;
    
    // Multi-level pointer
    int **secondLevel = &firstLevel;
    
    // Modify original through different access methods
    *firstLevel = 87;          // Direct modification via first-level pointer
    **secondLevel = 87;        // Modification via second-level pointer
    
    // Note: The pointer variable address itself cannot be modified
    // The pointer stores an address that can be changed, but the address
    // stored in memory (the pointer variable) is what we manipulate
}