学步园

struct Dijkstra {
	typedef long long int64;
	static const int64 INF = (int64) (1) << 60;
	struct Edge {
		Edge *next;
		int to;
		int64 dis;
	} ep[MAXE];
	Edge* g[MAXV];
	int heap[MAXV], inhp[MAXV];
	int64 d[MAXV];
	int V;
	int eN, hsize;
	//[0,n)
	inline void init(int n) {
		memset(g, 0, sizeof(g));
		V = n;
		eN = -1;
	}
	void addEdge(int u, int v, int64 dd) {
		ep[++eN].to = v;
		ep[eN].dis = dd;
		ep[eN].next = g[u];
		g[u] = &ep[eN];
	}
	void sift(int r) {
		int s = r;
		int fa;
		while ((fa = s << 1) <= hsize) {
			int p = fa, q = fa + 1;
			if (q <= hsize && d[heap[q]] < d[heap[p]])
				p = q;
			if (d[heap[p]] < d[heap[s]]) {
				inhp[heap[p]] = s;
				inhp[heap[s]] = p;
				swap(heap[p], heap[s]);
			} else break;
			s = p;
		}
	}
	int extractMin() {
		int res = heap[1];
		inhp[heap[hsize]] = 1;
		heap[1] = heap[hsize--];
		sift(1);
		return res;
	}
	void decreaseKey(int v, int64 ndis) {
		d[v] = ndis;
		int p = inhp[v];
		int fa;
		while (p > 1 && d[heap[p]] < d[heap[fa = (p >> 1)]]) {
			inhp[heap[p]] = fa;
			inhp[heap[fa]] = p;
			swap(heap[fa], heap[p]);
			p = fa;
		}
	}

	void solve(int source, int sink) {
		static bool ok[MAXV];
		memset(ok,false,sizeof(ok));
		inhp[source] = 1;
		ok[source] = true;
		heap[1] = source;
		hsize = 1;
		for (int i = 0; i < V; i++) d[i] = INF;
		d[source] = 0;
		for (int i = 0; i < V; i++) {
			if (i != source) {
				heap[++hsize] = i;
				inhp[i] = hsize;
			}
		}
		while (hsize > 0) {
			int u = extractMin();
			ok[u] = true;
			if (u == sink) return;
			for (Edge* i = g[u]; i; i = i->next) {
				if (!ok[i->to] && i->dis + d[u] < d[i->to]) {
					decreaseKey(i->to, i->dis + d[u]);
				}
			}
		}
	}
} g;