我用的是dij堆优化，

理论时间复杂度 $O(Nlog_N + 2 * E)$

本题 $N <= 10^5, M <= 2 * 10^5$

虽然stl有常数， 但是也不至于超时

理论上似乎不会超时， 但是 我TLE #1 #5

是我哪里写错了吗？

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>
#include<iostream>
const int N = 100000;
using namespace std;

int n, m, s, dis[N + 5];
priority_queue< pair<int, int > > q;
vector<pair<int, int> > edge[N + 5];

void read(int &x) {
	x = 0; char c = getchar();int w = 1;
	for(; c < '0' || c > '9'; c = getchar())
		if (c == '-')
			w = -1;
	for(; c <= '9' && c >= '0'; c = getchar())
		x = x * 10 + c - '0';
	x = x * w;  			
}

int main() {
	memset(dis, 0x3f, sizeof(dis));
	read(n);read(m);read(s);
	for(int i = 1; i <= m; ++i) {
		int u, v, w;
		read(u);read(v);read(w);
		edge[u].push_back(make_pair(v, w));
	}
	dis[s] = 0;
	q.push(make_pair(0, s));
	while(!q.empty()) {
		int v = q.top().second, val = q.top().first;
		q.pop();
		for(int i = 0; i < edge[v].size(); ++i)
			if (edge[v][i].second + dis[v] < dis[edge[v][i].first]) {
				// cout << v << " " << edge[v][i].first << endl; 
				dis[edge[v][i].first] = edge[v][i].second + dis[v];
				q.push(make_pair(dis[edge[v][i].first], edge[v][i].first));
			}
	}
	for(int i = 1; i <= n; ++i)
		printf("%d ", dis[i]);
	cout << endl;	
	return 0;
}