D02 最短路 Dijkstra 算法

#include<bits/stdc++.h>//标程：dijkstra+堆优化
using namespace std;
typedef pair<int,int> PII;
const int N=1e4+10;
vector< PII >G[N];
int n,m,st,ed,dis[N],vis[N];
void dijkstra()
{
    memset(dis,0x3f,sizeof(dis));dis[st]=0;
    memset(vis,0,sizeof(vis));
    priority_queue<PII,vector<PII>,greater<PII>>q;   q.push({0,st});
    while( q.size() )
    {
        int x=q.top().second; q.pop();
		if(vis[x])continue;
		vis[x]=1;
        for(auto i:G[x])//for(int i=0;i<=G[x].size()-1;i++)
		{
			int y=i.first,w=i.second;//int y=G[x][i].first,w=G[x][i].second;
			if(dis[y]>dis[x]+w)
			{
				dis[y]=dis[x]+w;
				q.push({dis[y],y});
			}
		}
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int i=1,x,y,w;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        G[x].push_back({y,w});
        G[y].push_back({x,w});
    }
    dijkstra();
    printf("%d\n",dis[ed]);
    return 0;
}


#include<bits/stdc++.h>//spfa
using namespace std;
typedef pair<int,int> PII;
const int N=1e4+10;
vector< PII >G[N];
int n,m,st,ed,d[N];bool v[N];
void spfa()
{
    memset(d,0x3f,sizeof(d));d[st]=0;
    memset(v,0,sizeof(v));v[st]=1;
    queue<int>q;
	q.push(st);
    while(!q.empty())
    {
        int x=q.front();q.pop();
		v[x]=0;
        for(auto i:G[x])
		{
			int y=i.first,w=i.second;
			if(d[y]>d[x]+w)
			{
				d[y]=d[x]+w;
				if(!v[y])q.push(y),v[y]=1;
			}
		}
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int i=1,x,y,w;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&w);
        G[x].push_back({y,w});
        G[y].push_back({x,w});
    }
    spfa();
    printf("%d\n",d[ed]);
    return 0;
}


#include<bits/stdc++.h>//spfa（前向星，scy又名：边目录）
using namespace std;
const int N=1e4+10;
struct edge{int x,y,w,pre;}a[N<<1];int alen,last[N];
void ins(int x,int y,int w)//ins函数的功能是建立一条从x出发到y且长度为w的边
{
    a[++alen]=edge{x,y,w,last[x]}; //全局增加一条有向边，并赋值
    last[x]=alen;                  //建立边与边的联系（都是从x出发）
}
int n,m,st,ed,d[N];bool v[N];
void spfa()
{
    memset(d,0x3f,sizeof(d));d[st]=0;
    memset(v,0,sizeof(v));v[st]=1;
    queue<int>q;
	q.push(st);
    while(!q.empty())
    {
        int x=q.front();q.pop();
		v[x] = 0;                     
        for(int k=last[x];k;k=a[k].pre)
        {
            int y=a[k].y,w=a[k].w;
            if(d[y]>d[x]+w)
            {
                d[y]=d[x]+w;
                if(!v[y])q.push(y),v[y]=1;
            }
        }  
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    alen=0;memset(last,0,sizeof(last)); //注意构图之前一定要初始化，不然后果很严重！
    for(int i=1,x,y,w;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&w); //题目给出的是无向边，而我们的边目录是有向边
        ins(x,y,w);
        ins(y,x,w); //建立正向边、反向边
    }
    spfa();
    printf("%d", d[ed]);
    return 0;
}