異なる条件に基づいてグラフ内の2つのノード間の最短経路

Question

私はHackerrankのthis問題を解決しようとしていました。当初、私はこれがダイクストラの直接的な実装であると考えていましたが、そうではありませんでした。

私が書いたコードは

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

である私が持っているアプローチは非常に単純です。各頂点では、それが出て行くエッジを消費し、active_verticesを更新します。頂点がまだ訪問されていなければ、更新されたコストです。また、min_distanceベクトルはこれまでの最小距離を記録します。

しかし、これはテストケースの半分で失敗します。私は、入力ファイルが多数のエッジを持ち、再作成するのがなぜ難しいのかを知ることができません。

私の現在のアプローチで何が問題になっているかを助けてくれるといいと思いますし、実行時間が指数関数的であれば少し混乱しています。 このコードの実行時間はどのくらいですか？

Answer 1

あなたはこれを逃しました：複数のエッジが許可されています。そのため、使用するエッジを選択する必要があります（必ずしもCが最小のものである必要はありません）。