#include<bits/stdc++.h>
using namespace std;
int a[10005][10005];
int d[10005],i,j;
const int INF=1e9;
int t;
int read()
{
int x=0,y=1;
char c;
while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*y;
}
void dij(int n)//单源最短路径
{
bool f[10005]={0};
f[1]=1;
int v;
for(i=1;i<n;i++)
{
int min=INF;
for(j=1;j<=n;j++)
{
if(!f[j]&&min>d[j])//找未标记中最小的
{
min=d[j];
v=j;
}
}
f[v]=1;//标记
for(j=v;j<=n;j++)
{
if(!f[j]&&a[v][j]+d[v]<d[j])//更新路径长度
{
d[j]=a[v][j]+d[v];
}
}
}
}
int main()
{
int n,m,x,y,z;
n=read(),m=read(),t=read();
for(i=1;i<=m;i++)
{
x=read(),y=read(),z=read();
a[x][y]=z;
}
for(i=1;i<=n;i++)
{
d[i]=a[t][i];//路径长度初始化]]
}
dij(n);
for(i=1;i<=n;i++)
{
printf("%d\n",d[i]);
}
return 0;
}
爆TLE，请问这个程序哪里出了问题？
