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)）

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)）

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 总体上就这些内容了，那么接下来就可以编码了。

参考代码

#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。