Ruta con suma mínima XOR de aristas en un gráfico dirigido

Dado un grafo dirigido con N Nodes y E aristas, un origen S y un destino D Nodes. La tarea es encontrar el camino con la mínima suma XOR de aristas de S a D. Si no hay una ruta de S a D , imprima -1 .

Ejemplos:  

Entrada: N = 3, E = 3, Bordes = {{{1, 2}, 5}, {{1, 3}, 9}, {{2, 3}, 1}}, S = 1 y D = 3 
Salida: 4 
La ruta con el XOR más pequeño del peso de los bordes será 1->2->3 
con la suma de XOR como 5^1 = 4.

Entrada: N = 3, E = 3, Bordes = {{{3, 2}, 5}, {{3, 3}, 9}, {{3, 3}, 1}}, S = 1 y D = 3 
Salida: -1 

Enfoque: La idea es utilizar el algoritmo de ruta más corta de Dijkstra con una ligera variación. A continuación se muestra el enfoque paso a paso para el problema: 

• Caso base: si el Node de origen es igual al destino, devuelve 0 .
• Inicialice una cola de prioridad con el Node de origen y su peso como 0 y una array visitada .
• Mientras que la cola de prioridad no está vacía: 
  1. Extraiga el elemento superior de la cola de prioridad. Llamémoslo como Node actual.
  2. Compruebe si el Node actual ya ha sido visitado con la ayuda de la array visitada. Si es así, continúe.
  3. Si el Node actual es el Node de destino, devuelva la distancia de suma XOR del Node actual desde el Node de origen.
  4. Itere todos los Nodes adyacentes al Node actual y empuje a la cola de prioridad y su distancia como suma XOR con la distancia actual y el peso del borde.
• De lo contrario, no hay ruta desde el origen hasta el destino. Por lo tanto, devuelve -1

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the smallest
// xor sum of edges
double minXorSumOfEdges(
    int s, int d,
    vector<vector<pair<int, int> > > gr)
{
    // If the source is equal
    // to the destination
    if (s == d)
        return 0;
 
    // Initialise the priority queue
    set<pair<int, int> > pq;
    pq.insert({ 0, s });
 
    // Visited array
    bool v[gr.size()] = { 0 };
 
    // While the priority-queue
    // is not empty
    while (pq.size()) {
 
        // Current node
        int curr = pq.begin()->second;
 
        // Current xor sum of distance
        int dist = pq.begin()->first;
 
        // Popping the top-most element
        pq.erase(pq.begin());
 
        // If already visited continue
        if (v[curr])
            continue;
 
        // Marking the node as visited
        v[curr] = 1;
 
        // If it is a destination node
        if (curr == d)
            return dist;
 
        // Traversing the current node
        for (auto it : gr[curr])
            pq.insert({ dist ^ it.second,
                        it.first });
    }
 
    // If no path exists
    return -1;
}
 
// Driver code
int main()
{
    int n = 3;
 
    // Graph as adjacency matrix
    vector<vector<pair<int, int> > >
        gr(n + 1);
 
    // Input edges
    gr[1].push_back({ 3, 9 });
    gr[2].push_back({ 3, 1 });
    gr[1].push_back({ 2, 5 });
 
    // Source and destination
    int s = 1, d = 3;
 
    cout << minXorSumOfEdges(s, d, gr);
 
    return 0;
}

// Java implementation of the approach
import java.util.PriorityQueue;
import java.util.ArrayList;
 
class Pair implements Comparable<Pair>
{
    int first, second;
 
    public Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
 
    @Override
    public int compareTo(Pair p)
    {
        if (this.first == p.first)
        {
            return this.second - p.second;
        }
        return this.first - p.first;
    }
}
 
class GFG{
 
// Function to return the smallest
// xor sum of edges
static int minXorSumOfEdges(int s, int d, 
                            ArrayList<ArrayList<Pair>> gr)
{
     
    // If the source is equal
    // to the destination
    if (s == d)
        return 0;
 
    // Initialise the priority queue
    PriorityQueue<Pair> pq = new PriorityQueue<>();
    pq.add(new Pair(0, s));
 
    // Visited array
    boolean[] v = new boolean[gr.size()];
 
    // While the priority-queue
    // is not empty
    while (!pq.isEmpty())
    {
         
        // Iterator<Pair> itr = pq.iterator();
        // Current node
        Pair p = pq.poll();
        int curr = p.second;
 
        // Current xor sum of distance
        int dist = p.first;
 
        // If already visited continue
        if (v[curr])
            continue;
 
        // Marking the node as visited
        v[curr] = true;
 
        // If it is a destination node
        if (curr == d)
            return dist;
 
        // Traversing the current node
        for(Pair it : gr.get(curr))
            pq.add(new Pair(dist ^ it.second, it.first));
    }
 
    // If no path exists
    return -1;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 3;
     
    // Graph as adjacency matrix
    ArrayList<ArrayList<Pair>> gr = new ArrayList<>();
    for(int i = 0; i < n + 1; i++)
    {
        gr.add(new ArrayList<Pair>());
    }
 
    // Input edges
    gr.get(1).add(new Pair(3, 9));
    gr.get(2).add(new Pair(3, 1));
    gr.get(1).add(new Pair(2, 5));
 
    // Source and destination
    int s = 1, d = 3;
    System.out.println(minXorSumOfEdges(s, d, gr));
}
}
 
// This code is contributed by sanjeev2552

# Python3 implementation of the approach
from collections import deque
 
# Function to return the smallest
# xor sum of edges
def minXorSumOfEdges(s, d, gr):
     
    # If the source is equal
    # to the destination
    if (s == d):
        return 0
 
    # Initialise the priority queue
    pq = []
    pq.append((0, s))
 
    # Visited array
    v = [0] * len(gr)
 
    # While the priority-queue
    # is not empty
    while (len(pq) > 0):
        pq = sorted(pq)
 
        # Current node
        curr = pq[0][1]
 
        # Current xor sum of distance
        dist = pq[0][0]
 
        # Popping the top-most element
        del pq[0]
 
        # If already visited continue
        if (v[curr]):
            continue
 
        # Marking the node as visited
        v[curr] = 1
 
        # If it is a destination node
        if (curr == d):
            return dist
 
        # Traversing the current node
        for it in gr[curr]:
            pq.append((dist ^ it[1],
                              it[0]))
    # If no path exists
    return -1
 
# Driver code
if __name__ == '__main__':
     
    n = 3
     
    # Graph as adjacency matrix
    gr = [[] for i in range(n + 1)]
 
    # Input edges
    gr[1].append([ 3, 9 ])
    gr[2].append([ 3, 1 ])
    gr[1].append([ 2, 5 ])
 
    # Source and destination
    s = 1
    d = 3
 
    print(minXorSumOfEdges(s, d, gr))
     
# This code is contributed by mohit kumar 29

// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
 
  // Function to return the smallest
  // xor sum of edges
  static int minXorSumOfEdges(int s, int d, List<List<Tuple<int,int>>> gr)
  {
 
    // If the source is equal
    // to the destination
    if (s == d)
      return 0;
 
    // Initialise the priority queue
    List<Tuple<int,int>> pq = new List<Tuple<int,int>>();
    pq.Add(new Tuple<int,int>(0, s));
 
    // Visited array
    int[] v = new int[gr.Count];
 
    // While the priority-queue
    // is not empty
    while (pq.Count > 0)
    {
      pq.Sort();
 
      // Current node
      int curr = pq[0].Item2;
 
      // Current xor sum of distance
      int dist = pq[0].Item1;
 
      // Popping the top-most element
      pq.RemoveAt(0);
 
      // If already visited continue
      if(v[curr] != 0)
        continue;
 
      // Marking the node as visited
      v[curr] = 1;
 
      // If it is a destination node
      if (curr == d)
        return dist;
 
      // Traversing the current node
      foreach(Tuple<int,int> it in gr[curr])
      {
        pq.Add(new Tuple<int,int>(dist ^ it.Item2, it.Item1));
      }
    }
 
    // If no path exists
    return -1;
  }
 
  // Driver code
  static void Main()
  {
    int n = 3;
 
    // Graph as adjacency matrix
    List<List<Tuple<int,int>>> gr = new List<List<Tuple<int,int>>>();
 
    for(int i = 0; i < n + 1; i++)
    {
      gr.Add(new List<Tuple<int,int>>());
    }
 
    // Input edges
    gr[1].Add(new Tuple<int,int>(3, 9));
    gr[2].Add(new Tuple<int,int>(3, 1));
    gr[1].Add(new Tuple<int,int>(2, 5));
 
    // Source and destination
    int s = 1;
    int d = 3;
 
    Console.WriteLine(minXorSumOfEdges(s, d, gr));
  }
}
 
// This code is contributed by divyesh072019.

<script>
 
// Javascript implementation of the approach
 
// Function to return the smallest
// xor sum of edges
function minXorSumOfEdges(s, d, gr)
{
     
    // If the source is equal
    // to the destination
    if (s == d)
        return 0;
  
    // Initialise the priority queue
    let pq = [];
    pq.push([0, s]);
  
    // Visited array
    let v = new Array(gr.length);
  
    // While the priority-queue
    // is not empty
    while (pq.length != 0)
    {
        pq.sort(function(a, b){return a[0] - b[0];});
         
        // Iterator<Pair> itr = pq.iterator();
        // Current node
        let p = pq.shift();
        let curr = p[1];
         
        // Current xor sum of distance
        let dist = p[0];
         
        // If already visited continue
        if (v[curr])
            continue;
         
        // Marking the node as visited
        v[curr] = true;
         
        // If it is a destination node
        if (curr == d)
            return dist;
         
        // Traversing the current node
        for(let it = 0; it < gr[curr].length; it++)
            pq.push([dist ^ gr[curr][it][1],
                            gr[curr][it][0]]);
    }
  
    // If no path exists
    return -1;
}
 
// Driver code
let n = 3;
  
// Graph as adjacency matrix
let gr = [];
for(let i = 0; i < n + 1; i++)
{
    gr.push([]);
}
 
// Input edges
gr[1].push([3, 9]);
gr[2].push([3, 1]);
gr[1].push([2, 5]);
 
// Source and destination
let s = 1, d = 3;
 
document.write(minXorSumOfEdges(s, d, gr));
 
// This code is contributed by unknown2108
 
</script>

4

Complejidad temporal: O((E + V) logV)