然后这是题解的
```cpp
#include<bits/stdc++.h>
#define maxn 10005
#define maxm 500005
#define inf 99999999
using namespace std;
int n,m,s,tot,dis[maxn],head[maxn];
bool vis[maxn];
struct Edge
{
int next,to,w;
}h[maxm];
void add(int u,int v,int w)
{
h[++tot].next=head[u];
h[tot].to=v;
h[tot].w=w;
head[u]=tot;
}
//初始化队列
queue<int> q;
void spfa()
{
for(int i=1; i<=n; i++)
{
dis[i]=inf;
}
int u,v;
q.push(s);
dis[s]=0;
while(!q.empty())
//当队列里没有元素的时候,那就已经更新了所有的单源最短路径
{
u=q.front();
//将队手节点记录并弹出队首节点
q.pop();
vis[u]=0;
for(int i=head[u];i;i=h[i].next)
//寻找与u相连的边
{
v=h[i].to;
if(dis[v]>dis[u]+h[i].w)
{
dis[v]=dis[u]+h[i].w;
//松弛操作,和floyd比较相似
if(!vis[v])
{
//已经在队列里的点就不用再进入了
vis[v]=1;
q.push(v);
}
}
}
}
}
int main(){
cin>>n;cin>>m;cin>>s;
for(int i=1,u,v,w;i<=m;i++)
{
cin>>u;/*起点*/cin>>v;/*终点*/cin>>w;/*权值*/
add(u,v,w);
}
spfa();
for(int i=1; i<=n; i++)
{
cout<<dis[i]<<" ";
}
return 0;
}
```
by cooronx @ 2019-05-14 18:19:30
可以解释一下题解里的那个head数组和h的next是什么意思吗?-_-
谢谢啦
by cooronx @ 2019-05-14 18:20:45