#include<iostream>
#include<queue>
#include<cstring>
const int INF=0x3f3f3f3f;
using namespace std;
struct node
{
int data,pos;
node(int x,int y){data=x;pos=y;}
bool operator <(const node &a) const
{
return data>a.data;
}
};
vector<pair<int,int> >GV[10001];
priority_queue<node>Q;
int dist[10001],n;
bool visited[10001];
void dij(int m)
{
memset(dist,INF,sizeof dist);
dist[m]=0;
Q.push(node(0,m));
while (!Q.empty())
{
node temp=Q.top();
Q.pop();
if (visited[temp.pos]) continue;
int pos=temp.pos,data=temp.data;
for (int i=0; i<GV[pos].size(); i++)
if (data+GV[pos][i].second<dist[GV[pos][i].first])
{
dist[GV[pos][i].first]=data+GV[pos][i].second;
Q.push(node(dist[GV[pos][i].first],GV[pos][i].first));
}
visited[pos]=true;
}
}
int main()
{
int v,m,x,y,data;
//n个节点,v组数据,从m出发
cin>>n>>v>>m;
for (int i=1; i<=v; i++)
{
cin>>x>>y>>data;
//从x走向y的距离为data
GV[x].push_back(make_pair(y,data));
GV[y].push_back(make_pair(x,data));//双向
}
dij(m);//从m开始
//输出所有节点到m的最短路径
for (int i=1; i<=n; i++)
cout<<dist[i]<<' ';
cout<<endl;
return 0;
}
文章评论