dijstra

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=10010,MAXM=500010;
int inf=2147483647;
struct XY{
   
	int w,to,pre;
}e[MAXM];
 
struct XX{
   
	int dis,num;
}d[MAXN],tmp;
 
struct cmp1{
   
	bool operator ()(XX &a,XX &b){
   
		return a.dis>b.dis;
	}
};
 
int n,m,s,sz=0;
int las[100010];
bool flag[MAXN];
priority_queue<XX,vector<XX>,cmp1> q;
 
 
void add(int x,int y,int w){
   
	++sz;e[sz].to=y;e[sz].w=w;e[sz].pre=las[x];las[x]=sz;
}
 
 
void Dijkstra(){
   
	int min,u=0;
	d[s].dis=0;q.push(d[s]);
	while (!q.empty()){
   
		u=q.top().num;q.pop();
		if (flag[u]) continue;
		flag[u]=true;
		
		for (int j=las[u];j;j=e[j].pre){
   
			int mu=e[j].to;
			if (d[mu].dis>d[u].dis+e[j].w){
   
				d[mu].dis=d[u].dis+e[j].w;
				q.push(d[mu]);
			}
		}
	}
}
 
 
int main(){
   
	int xx,yy,zz;
	cin >>n>>m>>s;
	for (int i=1;i<=n;++i){
   
		d[i].num=i;d[i].dis=inf;
	}
	for (int i=1;i<=m;++i){
   
		scanf("%d%d%d",&xx,&yy,&zz);
		add(xx,yy,zz);
	}
	
	Dijkstra();
	
	for (int i=1;i<=n;++i)
		printf("%d ",d[i].dis);
	cout <<endl;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
#define maxm 500005
#define INF 1234567890
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;
}
struct Edge
{
   
    int u,v,w,next;
}e[maxm];
int head[maxn],cnt,n,m,s,vis[maxn],dis[maxn],pre[maxn];
struct node
{
   
    int w,now;
    inline bool operator <(const node &x)const
    //重载运算符把最小的元素放在堆顶（大根堆）
    {
   
        return w>x.w;//这里注意符号要为'>'
    }
};
priority_queue<node>q;
//优先队列，其实这里一般使用一个pair，但为了方便理解所以用的结构体
inline void add(int u,int v,int w)
{
   
    e[++cnt].u=u;
    //这句话对于此题不需要，但在缩点之类的问题还是有用的
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    //存储该点的下一条边
    head[u]=cnt;
    //更新目前该点的最后一条边（就是这一条边）
}
//链式前向星加边

void print(int x)
{
   
	if(pre[x]==0)return ;
	print(pre[x]);
	cout<<"-> "<<x;
}
void dijkstra()
{
   
    for(int i=1;i<=n;i++)
    {
   
        dis[i]=INF;
    }
    dis[s]=0;
    //赋初值
    q.push((node){
   0,s});
    while(!q.empty())
    //堆为空即为所有点都更新
    {
   
        node x=q.top();
        q.pop();
        int u=x.now;
        //记录堆顶（堆内最小的边）并将其弹出
        if(vis[u]) continue; 
        //没有遍历过才需要遍历
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next)
        //搜索堆顶所有连边
        {
   
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w)
            {
   
                dis[v]=dis[u]+e[i].w;
                pre[v]=u;
                //松弛操作
                q.push((node){
   dis[v],v});
                //把新遍历到的点加入堆中
            }
        }
    }
}
int main()
{
   
    n=read(),m=read(),s=read();
    for(int i=1,x,y,z;i<=m;i++)
    {
   
        x=read(),y=read(),z=read();
        add(x,y,z);
    }
    dijkstra();
    for(int i=1;i<=n;i++)
    {
   
        printf("%d ",dis[i]);
 // print(i);
  // cout<<endl;
    }
    return 0;
}

SPFA

void SPFA(int x)
{
   
	d[x]=0;
	for(int i=1;i<=n;i++)
	d[i]=+OO;
	queue<int>Q;
	Q.push(x);
	inq[x]=true;
	while(!Q.empty())
	{
   
		int k=Q.front;Q.pop();inq[k]=false;
		for(int i=head[k];i!=0;i=edge[i].next)
		{
   
			int j=edge[i].u ;
			if(d[j]>d[k]+edge[i].w )
			{
   
				d[j]=d[k]+edge[i].w;
				if(inq[j]!){
   
					Q.push(j);
					inq[k]=true;
				} 
			}
		}
	}
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
const long long inf=2147483647;
const int maxn=10005;
const int maxm=500005;
using namespace std;
int n,m,s,num_edge=0;
int dis[maxn],vis[maxn],head[maxm];
struct Edge
{
   
  int next,to,dis;
}edge[maxm]; //结构体表示静态邻接表
void addedge(int from,int to,int dis) //邻接表建图
{
    //以下是数据结构书上的标准代码，不懂翻书看解释
  edge[++num_edge].next=head[from]; //链式存储下一条出边
  edge[num_edge].to=to; //当前节点编号
  edge[num_edge].dis=dis; //本条边的距离
  head[from]=num_edge; //记录下一次的出边情况
}
void spfa()
{
   
  queue<int> q; //spfa用队列，这里用了STL的标准队列
  for(int i=1; i<=n; i++) 
  {
   
    dis[i]=inf; //带权图初始化
    vis[i]=0; //记录点i是否在队列中，同dijkstra算法中的visited数组
  }
  q.push(s); dis[s]=0; vis[s]=1; //第一个顶点入队，进行标记
  while(!q.empty())
  {
   
    int u=q.front(); //取出队首
    q.pop(); vis[u]=0; //出队标记
    for(int i=head[u]; i; i=edge[i].next) //邻接表遍历，不多解释了（也可用vector代替）
    {
   
      int v=edge[i].to; 
      if(dis[v]>dis[u]+edge[i].dis) //如果有最短路就更改
      {
   
        dis[v]=dis[u]+edge[i].dis;
        if(vis[v]==0) //未入队则入队
        {
   
          vis[v]=1; //标记入队
          q.push(v);
        }
      }
    }
  }
}
int main()
{
   
  cin>>m>>n;
  s=n;
  for(int i=1; i<=m; i++)
  {
   
    int f,g,w;
    cin>>f>>g>>w; 
    addedge(f,g,w); //建图，有向图连一次边就可以了
    addedge(g,f,w);
  }
   spfa(); //开始跑spfa
	cout<<dis[1]<<endl; //否则打印最短距离
  return 0;
}