文章

10

粉丝

76

获赞

78

访问

4.0k

头像
P1565 最短路 答疑提问:
P1565 中国科学院大学2021年机试题
发布于2025年2月23日 21:05
阅读数 107

您好,我看高分篇说如果spfa超时可以改成优先队列,请问一下是这样改吗
原版:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 1005;
struct Edge {
    int b, c;
};
int n, m;
void spfa(int s, int dis[], int vis[], vector<Edge> g[], int pre[]) {
    for (int i = 1; i <= n; i++)
        dis[i] = INF;
    queue<int> q;
    dis[s] = 0;
    vis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int t = q.front();
        vis[t] = 0;
        q.pop();
        for (int i = 0; i < g[t].size(); i++) {
            Edge e = g[t][i];
            if (dis[t] + e.c < dis[e.b]) {
     &nbs...

登录查看完整内容


登录后发布评论

1 条评论
admin SVIP
2025年2月23日 23:12

嗯,能AC就行,改了之后复杂度不稳定,还不行就用dijkstra。

赞(0)