使用最小堆dijk求最短路径的标准算法,时间复杂度为elogv。
#include <cstdio>#include <string>#define INF 2000000000#define MAXN 500000#define MAXM 500000int T, N, M;int dist[MAXN], next[2][MAXM], num[2][MAXN], heap[MAXN], idx[MAXN], used[MAXN];int size, src, dst;typedef struct...{ int u, v, w;} Edge;Edge e[2][MAXM];void update ( int );int get_top ();void printHeap ()...{ int i; for ( i = 1; i <= size; i ++ ) printf ( "%d ", heap[i] ); printf ( " " );}void......
阅读全文