D02 最短路 Dijkstra 算法

#include<bits/stdc++.h>//标程：dijkstra+堆优化
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
vector< PII >G[N];
int n,m,st,ed,dis[N],vis[N];
void dij()
{
    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",&n,&m,&st);
    for(int i=1,x,y,w;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        G[x].push_back({y,w});
    }
    dij();
    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
    return 0;
}

/*
#include<bits/stdc++.h>//spfa ，超时
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10;
vector< PII >G[N];
int n,m,st,ed,dis[N];bool v[N];
void spfa()
{
    memset(dis,0x3f,sizeof(dis));dis[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(dis[y]>dis[x]+w)
			{
				dis[y]=dis[x]+w;
				if(!v[y])q.push(y),v[y]=1;
			}
		}
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&st);
    for(int i=1,x,y,w;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&w);
        G[x].push_back({y,w});
    }
    spfa();
    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
    return 0;
}


#include<bits/stdc++.h>//spfa（前向星，scy又名：边目录）
using namespace std;
const int N=1e5+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,dis[N];bool v[N];
void spfa()
{
    memset(dis,0x3f,sizeof(dis));dis[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(dis[y]>dis[x]+w)
            {
                dis[y]=dis[x]+w;
                if(!v[y])q.push(y),v[y]=1;
            }
        }  
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&st);
    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);
    }
    spfa();
    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
    return 0;
}

*/