文章
10
粉丝
76
获赞
78
访问
4.0k
您好,我看高分篇说如果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...
登录后发布评论
嗯,能AC就行,改了之后复杂度不稳定,还不行就用dijkstra。