ダイクストラ法の質問

Question

：

#define MAX_VERTICES 260000 

#include <fstream> 
#include <vector> 
#include <queue> 
#define endl '\n' 
using namespace std; 

struct edge { 
    int dest; 
    int length; 
}; 

bool operator< (edge e1, edge e2) { 
    return e1.length > e2.length; 
} 

int C, P, P0, P1, P2; 
vector<edge> edges[MAX_VERTICES]; 
int best1[MAX_VERTICES]; 
int best2[MAX_VERTICES]; 

void dijkstra (int start, int* best) { 
    for (int i = 0; i < P; i++) best[i] = -1; 
    best[start] = 0; 
    priority_queue<edge> pq; 
    edge first = { start, 0 }; 
    pq.push(first); 
    while (!pq.empty()) { 
     edge next = pq.top(); 
     pq.pop(); 
     if (next.length != best[next.dest]) continue; 
     for (vector<edge>::iterator i = edges[next.dest].begin(); i != edges[next.dest].end(); i++) { 
      if (best[i->dest] == -1 || next.length + i->length < best[i->dest]) { 
       best[i->dest] = next.length + i->length; 
       edge e = { i->dest, next.length+i->length }; 
       pq.push(e); 
      } 
     } 
    } 
} 

int main() { 
    ifstream inp("apple.in"); 
    ofstream outp("apple.out"); 

    inp >> C >> P >> P0 >> P1 >> P2; 
    P0--, P1--, P2--; 
    for (int i = 0; i < C; i++) { 
     int a, b; 
     int l; 
     inp >> a >> b >> l; 
     a--, b--; 
     edge e = { b, l }; 
     edges[a].push_back(e); 
     e.dest = a; 
     edges[b].push_back(e); 
    } 

    dijkstra (P1, best1);   // find shortest distances from P1 to other nodes 
    dijkstra (P2, best2);   // find shortest distances from P2 to other nodes 

    int ans = best1[P0]+best1[P2]; // path: PB->...->PA1->...->PA2 
    if (best2[P0]+best2[P1] < ans) 
     ans = best2[P0]+best2[P1]; // path: PB->...->PA2->...->PA1 
    outp << ans << endl; 
    return 0; 
} 

、これはどのようなものです：のために使用さif (next.length != best[next.dest]) continue;？ループを通って私たちがすでに持っているのと同じ答えを与える私たちの状況を避けるのはそれですか？

ありがとうございます！

Answer 1

この行は、C++のpriority_queueにreduce_key関数がないことを処理する方法です。

つまり、pq.push(e)を実行したときに、既に同じ宛先のエッジがヒープにある場合は、ヒープ内のエッジのキーを減らすことをお勧めします。これはC++のpriority_queueでは簡単にはできません。したがって、簡単な方法は、同じ宛先に対応するヒープ内の複数のエッジを許可し、ヒープから最初にポップする（各destに対して）を無視することです。

これにより、複雑さがO(ElogV)からO(ElogE)に変更されることに注意してください。

Answer 2

priority_queueに同じエッジが2回含まれていても、それぞれが異なる「長さ」を持つケースが考えられます。

これは、長さがYであり、その後に再びエッジXを押すと発生する可能性がありますが、今回は長さが<Yです。そのため、そのエッジの長さがあなたが今までにそのエッジのために見つけた最も低いもの、あなたはそのループの反復でそれを無視します。