模板题
单源点最短路径
存图方式
链式前向星
只需要开一个数组存储每个点引出的第一条边，然后存储每个点作为起点的每条边，这样就可以做到不重不漏。
定义一个结构体、一个数组和一个变量
struct EDGE
{
int next;
int to;
}edge[1000000];
int head[1000000];
int cnt=0;//指针
起点是用head存储的，其(带权重)构建的完整代码如下
#include<iostream>
using namespace std;
struct edge
{
int next;
int to;
int w;
}edge[MAXM];
int head[MAXN];//head[i]为i点的第一条边
int cnt=0;
void addedge(int u,int v,int w) //起点，终点，权值
{
edge[++cnt].next=head[u];//更新cnt
edge[cnt].to=v;
edge[cnt].w=w;
head[u]=cnt;
}
int main()
{
int n;
for(int i=1;i<=n;i++)
{
int a,b,w;
addedge(a,b,w);
//如果是无向图，还要addedge(b,a,wei);
}
}
这里的next指的是遍历时的下一条边，head指的是遍历时的第一条边，而存边时相当于反过来操作，所以next记录上一条边，而head记录最后一条边。
边的遍历
for(int i=head[x];i!=0;i=edge[i].next)
这个循环的结束条件是i等于0，因为最后一条边，也就是存边时第一条边，在把head值存进next时，head还没有更新过，也就是0。所以当next返回0时，就说明这些边遍历完毕了。
构建有向图
SPFA
用队列来保存待优化的结点（类似于BFS），每次取出队首结点，并用队首节点来对最短路径进行更新并进行松弛操作
如果要对所邻接点的最短路径需要更新，且该点不在当前的队列中，就将该点加入队列
然后不断进行松弛操作，直至队列空为止。
#include<bits/stdc++.h>
using namespace std;
// 快读
inline int read()
{
int x=0,k=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*k;
}
#define maxn 10005
#define maxm 500005
#define inf 1234567890
int n,m,s,cnt,dis[maxn],head[maxn];
bool vis[maxn];
// 链式前向星
struct Edge
{
int next,to,w;
}ed[maxm];
void add(int u,int v,int w)
{
ed[++cnt].next=head[u];
ed[cnt].to=v;
ed[cnt].w=w;
head[u]=cnt;
}
queue<int> q;
inline void spfa()
{
for(int i=1; i<=n; i++) dis[i]=inf;//初始化
dis[s]=0; q.push(s); vis[s]=1; //赋初值
int u,v;
while(!q.empty())
{
u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=ed[i].next)
{
v=ed[i].to;
if(dis[u]+ed[i].w<dis[v])
{
dis[v]=dis[u]+ed[i].w;
if(!vis[v])
vis[v]=1, q.push(v);
}
}
}
}
int main(){
n=read(),m=read(),s=read();
for(int i=1,u,v,w;i<=m;i++)
{
u=read(),v=read(),w=read();
add(u,v,w);
}
spfa();
for(int i=1; i<=n; i++)
{
printf("%d ",dis[i]);
}
return 0;
}