Kürzester Pfad zwischen zwei Knoten in einem Diagramm basierend auf einer anderen Bedingung

Question

Ich habe versucht, this Problem auf Hackerrank zu lösen. Anfangs dachte ich, dass dies eine direkte Umsetzung von Dijkstra wäre, aber das sollte nicht sein.

Der Code, den ich geschrieben habe, ist

#include <iostream> 
#include <algorithm> 
#include <climits> 
#include <vector> 
#include <set> 
using namespace std; 

typedef struct edge { unsigned int to, length; } edge; 

int dijkstra(const vector< vector<edge> > &graph, int source, int target) { 
    vector<int> min_distance(graph.size(), INT_MAX); 
    min_distance[ source ] = 0; 
    std::vector<bool> visited(graph.size(), false); 
    set< pair<int,int> > active_vertices; 
    active_vertices.insert({0,source}); 
    while (!active_vertices.empty()) { 
     int where = active_vertices.begin()->second; 
     int where_distance = active_vertices.begin()->first; 
     visited[where] = true; 
     active_vertices.erase(active_vertices.begin()); 
     for (auto edge : graph[where]) 
     { 
      if(!visited[edge.to]) 
      { 
      int cost = where_distance | edge.length; 
      min_distance[edge.to] = min(cost, min_distance[edge.to]); 
      active_vertices.insert({cost, edge.to}); 
      } 
     } 
    } 
    return min_distance[target]; 
} 

int main(int argc, char const *argv[]) 
{ 
    unsigned int n, m, source, target; 
     cin>>n>>m; 
     std::vector< std::vector<edge> > graph(n, std::vector<edge>()); 
     while(m--) 
     { 
      unsigned int from, to, dist; 
      cin>>from>>to>>dist; 
      graph[from-1].push_back({ to-1, dist}); 
      graph[to-1].push_back({from-1, dist}); 
     } 
     cin>>source>>target; 
     cout<<dijkstra(graph, source-1, target-1)<<endl; 
    return 0; 
} 

Der Ansatz, die ich habe ist ziemlich einfach. An jedem Scheitelpunkt nehme ich die ausgehende Kante und aktualisiere die active_vertices mit ihren aktualisierten Kosten, vorausgesetzt, dass der Scheitelpunkt noch nicht besucht wurde. Auch ein min_distance Vektor verfolgt den minimalen Abstand bis jetzt.

Aber das scheitert für die Hälfte der Testfälle. Ich bin nicht in der Lage herauszufinden, warum aus der Eingabe als die Eingabedatei eine große Anzahl von Kanten hat und neu zu erstellen ist ziemlich schwierig.

Es wäre schön, wenn Sie mir helfen könnten, was mit meiner derzeitigen Herangehensweise nicht stimmt, und ich bin auch ein wenig verwirrt, wenn die Laufzeit exponentiell ist. Was wäre die Laufzeit dieses Codes?

Answer 1

Sie haben Folgendes vermisst: mehrere Kanten sind zulässig. Daher müssen Sie auswählen, welche Kante Sie verwenden möchten (nicht unbedingt die mit dem kleinsten C).