spfa竟然比dijkstra快了将近6倍.....

spfa 做法

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

using namespace std;

typedef pair<int,int> PII;

const int N = 3000;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], cnt[N], cow[N];
bool st[N]; //用于记录当前节点是否在队列中
int n, p, c;

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

int spfa(int x)
{
    memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    q.push(x);
    dist[x] = 0;
    st[x] = true;

    while(!q.empty())
    {
        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])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        if(dist[i] == 0x3f3f3f3f) return -1;
        res += dist[cow[i]];
    }

    return res;

}
int main()
{
    memset(h, -1, sizeof h);
    cin>>n>>p>>c;

    for(int i = 1; i <= n; i++) 
    {
        cin>>cow[i];
        cnt[cow[i]] ++;
    }

    for(int i = 0; i < c; i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        add(a, b, c), add(b, a, c);
    }

    int res = 0x3f3f3f3f;
    for(int i = 1; i <= p; i++)
    {
        int t = spfa(i);
        if(t != -1)
            res = min(res, t);
    }
    cout<<res<<endl;
    return 0;
}

堆优化dijkstra

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

using namespace std;

typedef pair<int,int> PII;

const int N = 3000;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], cnt[N], cow[N];
bool st[N]; //用于记录当前节点是否已经处理过
int n, p, c;

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

int dijkstra(int x)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push(make_pair(0, x));
    dist[x] = 0;

    while(heap.size())
    {
        int index = heap.top().second;
        int distance = heap.top().first;
        heap.pop();

        if(st[index]) continue; //当前节点已经求出最短路，直接跳过
        st[index] = true;

        for(int i = h[index]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push(make_pair(dist[j], j));
            }
        }
    }

    // for(int i = 1; i <= p; i++) if(dist[i] == 0x3f3f3f3f) return -1;

    // int res = 0;
    // for(int i = 1; i <= p; i++)
    // {
    //     res +=  cnt[i] * dist[i];
    // }

    // return res;

     int ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        int j = cow[i];
        if(dist[j] == 0x3f3f3f3f) return -1;
        ans += dist[j];
    }
    return ans;
}
int main()
{
    memset(h, -1, sizeof h);
    cin>>n>>p>>c;

    for(int i = 1; i <= n; i++) 
    {
        cin>>cow[i];
        cnt[cow[i]] ++;
    }

    for(int i = 0; i < c; i++)
    {
        int a, b, c;
        cin>>a>>b>>c;
        add(a, b, c), add(b, a, c);
    }

    int res = 0x3f3f3f3f;
    for(int i = 1; i <= p; i++)
    {
        int t = dijkstra(i);
        if(t != -1)
            res = min(res, t);
    }
    cout<<res<<endl;
    return 0;
}