dijkstra 邻接表 链式前向星性能差距大且TLE

dijkstra

邻接表做法：开O2 84pts 不开O2 48pts

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct edge {
    int v,w;

};
struct pt {
    int length,num;
    friend bool operator<(pt a,pt b) {
        return a.length > b.length;
    }
};

vector<edge> mp[100100];
int vis[100100],dist[100100];
int n,m,s;
int u,v,w;
void dijkstra(int st) {
    priority_queue<pt> q;
    q.push({0,st});
    for (int i = 1; i <= n; i++) {
        dist[i] = INT_MAX;

    }
    dist[st] = 0;
    while(q.size() != 0) {
        pt now = q.top();
        q.pop();
        vis[now.num] = 1;
        for (auto t:mp[now.num]) {
            if (vis[t.v] == 1) continue;
            //printf(" dist[%lld]= %lld t.w = %lld dist[t.v] = %lld\n",now.num,dist[now.num],t.w ,dist[t.v]); 
            if (dist[now.num] + t.w < dist[t.v]) {
                dist[t.v] = dist[now.num] + t.w;
                //printf("update dist[%lld] = dist[%lld]:%lld + %lld\n",t.v,now.num,dist[now.num],t.w); 
                q.push({dist[t.v],t.v});
            }
                //printf("now = [%lld,%lld] t = [%lld,%lld] dist[%lld]= %lld\n",now.length,now.num,t.v,t.w,t.v,dist[t.v]);
        }
    }
}
signed main() {
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        mp[u] .push_back({v,w});
    }

    dijkstra(s);
    for (int i= 1;i<= n;i++)
    {
        cout << dist[i]<< " ";
    }
}

链式前向星 都是48pts

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct edge
{
    int v,w,next;
}e[200010];
struct pt
{
    int num,d;
    friend bool operator<(pt a,pt b)
    {
        return a.d > b.d;
    }
};
int cnt,head[100010],vis[100010],dist[100010];
int u,v,w;
int n,m,s;

void add(int u,int v,int w)
{
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

void dijkstra(int st)
{
    for (int i = 1;i <= n;i++)
    {
        dist[i] = LLONG_MAX;
    }
    dist[st] = 0;
    priority_queue<pt > q;
    q.push({st,dist[st]});
    while (q.size())
    {
        pt now = q.top();
        q.pop();
        vis[now.num] = 1;
        //printf("now = %lld",now);
        for (int i = head[now.num];i;i = e[i].next)
        {
            if (vis[e[i].v] == 0)
            {
                if (dist[now.num] + e[i].w < dist[e[i].v])
                {
                    dist[e[i].v] = dist[now.num] + e[i].w;
                    q.push({e[i].v,dist[e[i].v]});

                    //printf("\tnow = %lld v = %lld (now,v) = %lld dist[now] = %lld dist[v] = %lld\n",now,e[i].v,e[i].w,dist[now],dist[e[i].v]);
                }
            }
        }
    }

}
signed main()
{
//  freopen("P4779_3.in","r",stdin);
//  freopen("P4779.out","w",stdout);
    cin >> n >> m >> s;
    for (int i = 1;i <= m;i++)
    {
        cin >> u >> v >> w;
        add(u,v,w);
    }
    dijkstra(s);

    for (int i = 1;i <= n;i++)
    {
        cout << dist[i] << " ";
    }
}

希望有dalao看看