SP23132 题解

题目分析

很明显，这是一道单源最短路的题，可以使用 Dijkstra 来做这道题（~~如果是骗分的也可以试试 Floyd~~），而且还可以说这就是一道 Dijkstra 的版子。

接下来我将会简单说一下 Dijkstra。

Dijkstra

这个算法可以简单概括为“Dijkstra = BFS + 贪心”，大体步骤如下：

步骤	做法	具体操作	结果
$1$	从起点 $s$ 出发，用 BFS 扩展它的邻居节点	把这些邻居点放到一个集合 $A$ 中，并记录这些点到 $s$ 的距离
$2$	选择距离 $s$ 最近的邻居 $v$ ，继续用 BFS 扩展 $v$ 的邻居	首先在 $A$ 中找到距离 $s$ 最小的点 $v$ ，把 $v$ 的邻居点放到 $A$ 中；如果 $v$ 的邻居经过 $v$ 中转，到 $s$ 的距离更短，则更新这些邻居到 $s$ 的距离；最后从集合 $A$ 中移走 $v$ ，后面不再处理 $v$	得到了从 $s$ 到 $v$ 的最短路径； $v$ 的邻居更新了到 $s$ 的距离
$3$	重复步骤 $2$ ，直到所有点都扩展到并计算完毕		集合 $A$ 为空。计算出所有点到 $s$ 的最短距离

按照这个步骤，实现 Dijkstra 其实并不难，现在给出参考实现代码。

实现

暴力做法（ $O(n^2)$ ）

CPP

struct edge {
  int v, w;
};

vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];

void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  dis[s] = 0;
  for (int i = 1; i <= n; i++) {
    int u = 0, mind = 0x3f3f3f3f;
    for (int j = 1; j <= n; j++)
      if (!vis[j] && dis[j] < mind) u = j, mind = dis[j];
    vis[u] = true;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;
    }
  }
}

优先队列做法（ $O(m\log m)$ ）

CPP

struct edge {
  int v, w;
};

struct node {
  int dis, u;

  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queue<node, vector<node>, greater<node>> q;

void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  memset(vis, 0, (n + 1) * sizeof(int));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}

Dijkstra 总体上就这些内容了，那么接下来就可以编码了。

参考代码

CPP

#include<bits/stdc++.h>
#define int long long
#define Rint register int
#define fast_running ios::sync_with_stdio(false),std::cin.tie(nullptr),std::cout.tie(nullptr)
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 5, M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int m, s, cnt;
int head[N], dist[N], flag[N];
priority_queue<PII, vector<PII>, greater<PII>> q;     //优先队列优化 
struct edge {
	int from, to, next, w;
} e[M << 1];
void addedge(int u, int v, int w) {                   //建图 
	e[++cnt].from = u;
	e[cnt].to = v;
	e[cnt].next = head[u];
	e[cnt].w = w;
	head[u] = cnt;
}
void init() {                                         //初始化 
	for (int i = 0; i < N; i++) {
		head[i] = -1;
		flag[i] = 0;
		dist[i] = INF;
	}
	cnt = 0;
	return;
}
void dijshort(int start) {                            //优先队列优化的 Dijkstra 
	dist[start] = 0;
	q.push({dist[start], start});
	while (!q.empty()) {
		PII tp = q.top();
		q.pop();
		int id_x = tp.second, dist_x = tp.first;
		if (flag[id_x]) continue;
		flag[id_x] = 1;
		for (int i = head[id_x]; i != -1; i = e[i].next) {
			int v = e[i].to;
			if (dist[v] > dist_x + e[i].w) {
				dist[v] = dist_x + e[i].w;
				q.push({dist[v], v});
			}
		}

	}
}
signed main() {
	fast_running;
	cin >> m;
	init();
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		addedge(u, v, w);
		addedge(v, u, w);
	}
	cin >> s;
	dijshort(s);
	int T, in;
	cin >> T;
	while (T--) {
		cin >> in;
		if (dist[in] == INF) cout << "NO PATH\n";
		else cout << dist[in] << '\n';
	}

	return 0;
}

AC 记录：https://www.luogu.com.cn/record/226070501。

文章操作

题目分析

Dijkstra

实现

暴力做法（ $O(n^2)$ ）

优先队列做法（ $O(m\log m)$ ）

参考代码

相关推荐

评论

SP23132 题解

文章操作

题目分析

Dijkstra

实现

暴力做法（O(n2)O(n^2)O(n2)）

优先队列做法（O(mlog⁡m)O(m\log m)O(mlogm)）

参考代码

相关推荐

评论

暴力做法（ $O(n^2)$ ）

优先队列做法（ $O(m\log m)$ ）