mle sssp
#include <iostream>
#include <queue>
using namespace std;
const unsigned short maxn=10005;
#define INT_MAX 2147483647
int map[maxn][maxn];
int n,m,s;
int f,g,w;
int result[maxn];
struct point
{
unsigned short dest[maxn];
unsigned short odlength=0;
};
point team[maxn];
struct unit
{
unsigned short num;
bool operator>(const unit& s)const{return result[num]>result[s.num];}
};
priority_queue<unit,vector<unit>,greater<unit> > q;
bool inqueue[maxn];
void relax(int s)
{
for(int i=0;i<=team[s].odlength;++i)
{
unsigned short &d=team[s].dest[i];
if(result[s]+map[s][d]<result[d])
{
result[d]=result[s]+map[s][d];
if(!inqueue[d])
{
q.push({d});
}
}
}
}
int main()
{
/* for(int i=1;i<maxn;++i)
{
result[i]=INT_MAX;
}
result[1]=5;
q.push({2});
q.push({1});
cout<<q.top().num<<" "<<result[q.top().num]<<endl;
result[2]=1;
cout<<q.top().num<<" "<<result[q.top().num]<<endl;
q.push({0});
q.pop();
cout<<q.top().num<<" "<<result[q.top().num]<<endl;*/ cin>>n>>m>>s;
for(int i=1;i<=n;++i)
{
result[i]=INT_MAX;
}
for(int i=0;i<m;++i)
{
cin>>f>>g>>w;
if(f==g)continue;
map[f][g]=(map[f][g]==0?w:min(map[f][g],w));
team[f].dest[team[f].odlength]=g;
team[f].odlength++;
}
result[s]=0;
q.push({s});
do
{
s=q.top().num;
inqueue[s]=false;
q.pop();
relax(s);
q.push({0});
q.pop();
}while(!q.empty());
for(int i=1;i<=n;++i)
{
cout<<result[i]<<" ";
}
cout<<endl;
return 0;
}