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

#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]<< " ";
	}
}

#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] << " ";
	}
}