Dijkstra算法全部TLE，SPFA算法4个TLE，2个AC……
第一次打最短路，请见谅QAQ……

#include<bits/stdc++.h>//dijkstra
using namespace std;
const int MAXN=1e5+5;
int n,m,s;
int u,v,w;
struct edge
{
	int v,w;
};
vector<edge> e[MAXN];
int dis[MAXN],vis[MAXN];
void work(int n,int s)
{
	memset(dis,0x3f3f3f3f,(n+1)*sizeof(int));
	dis[s]=0;
	for(int i=1;i<=n;i++)
	{
		int u=0,mind=0x3f3f3f3f;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&dis[j]<mind)
			{
				u=j;
				mind=dis[j];
			}
		vis[u]=true;
		for(auto ed:e[u])
		{
			int v=ed.v,w=ed.w;
			if(dis[v]>dis[u]+w)
				dis[v]=dis[u]+w;
		}
	}
}
int main(){
	scanf("%d %d %d ",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d ",&u,&v,&w);
		e[u].push_back(edge{v,w});
	}
	work(n,s);
	for(int i=1;i<=n;i++)
        printf("%d ",dis[i]);
	return 0;
}

#include<bits/stdc++.h>//SPFA
using namespace std;
const int MAXN=1e5+5;
int n,m,s;
int u,v,w;
struct edge
{
	int v,w;
};
vector<edge> e[MAXN];
int dis[MAXN],vis[MAXN],cnt[MAXN];
queue<int> q;
void work(int n,int s)
{
	memset(dis,0x3f3f3f3f,(n+1)*sizeof(int));
	dis[s]=0,vis[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto ed:e[u])
		{
			int v=ed.v,w=ed.w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n)
					return ;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return ;
}
int main(){
	scanf("%d %d %d ",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d ",&u,&v,&w);
		e[u].push_back(edge{v,w});
	}
	work(n,s);
	for(int i=1;i<=n;i++)
		printf("%d ",dis[i]);
	return 0;
}