【模板】Dijkstra算法

朴素算法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void dijkstra() { for (int i = 1; i <= n; i++) { int mink = 0; for (int j = 1; j <= n; j++) { if (!vis[j] && d[j] <= d[mink]) { mink = j; } } vis[mink] = true; for (Edge &e : g[mink]) { if (d[mink] < d[e.v] && d[mink] + e.w < d[e.v]) { d[e.v] = d[mink] + e.w; } } } } 堆优化 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void dijkstra() { while (!q.empty()) { int x = q.top().id; q.pop(); if (!vis[x]) { vis[x] = tru...