算法对比SPFA, dijkstra, 堆优化dijkstra 说明YXC NB

YXC 用的模拟循环队列， 但是开的数组大小只为n,由于存在双向边， 可能存在段错误的风险，但是y总直接弄个
if(hh == N)hh = 0;
if(tt == N)tt = 0;
循环队列
极大化利用了空间的效率
NB;

对比三种算法时间

从上自下依次为 dijkstra，堆优化dijkstra，SPFA.

自己体会

C++ 代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

const int N = 2510, M = 6200 * 2 + 10;

int h[N], e[M], ne[M], w[M], idx;
bool st[N];
int dist[N];
int n, m, S, T;

void add(int a, int b, int c)
{
    e[++ idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    w[idx] = c;
}

void SPFA()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    queue<int> q;
    q.push(S);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                st[j] = true, q.push(j);
            }
        }
    }
}

int main()
{
    memset(h, - 1, sizeof h);
    cin >> n >> m >> S >> T;
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    SPFA();
    cout << dist[T] << endl;
    return 0;
}