题目描述
给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。
数据保证你能从 s 出发到任意点。
输入格式
第一行为三个正整数n,m,s。 第二行起 m 行，每行三个非负整数 ui,vi,wi，表示从 ui 到 vi 有一条权值为 wi 的有向边。
输出格式
输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。
输入输出样例
输入
4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4
输出
0 2 4 3
这就是一道图。
但是用邻接矩阵太浪费空间了，还是用邻接表好一点，邻接表，用的是动态数组，这样会节省空间。
这里定义一个结构体node，里面两个int元素，to和dis，to是到达的节点，dis表示路径长度，让后建立动态数组a，数据类型设为node，输入时的存储就像这样：
a[u].push_back(node{v,w});
然后就是写搜索函数，这道题使用的算法是dijkstra
用在这道题上面，那就把点分为两种，蓝点和白点，蓝点就是没有确定最小值的，而白点就是已经确定了的，从s开始找他通往的所有蓝点y，用数组dis记录到达y点的长度，接着，再从剩下的蓝点中，找一个值最小的，标记为白点，以他为基础，查找与之相连的蓝点，如此循环
然后要注意，记录dis记录的同时，如果元素没被访问，就进行入队操作。
最后输出dis数组的值就行了
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,s;
struct node{
int to,dis;
friend bool operator <(node a,node b){
return a.dis>b.dis;
}
};
priority_queue<node>q;
vector<node>a[N];
int dis[N];
int vis[N];
void dij(){
for(int i=1;i<=n;i++)dis[i]=INT_MAX;
dis[s]=0;
q.push(node{s,0});
while(!q.empty()){
node t=q.top();
q.pop();
int x=t.to;
if(vis[x]==1)continue;
vis[x]=1;
for(int i=0;i<a[x].size();i++){
int y=a[x][i].to;
int z=a[x][i].dis;
dis[y]=min(dis[y],dis[x]+z);
if(vis[y]==0)q.push(node{y,dis[y]});
}
}
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&s);
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&u,&v,&w);
a[u].push_back(node{v,w});
}
dij();
for(int i=1;i<=n;i++)printf("%lld ",dis[i]);
}
