C++14(g++5.4) 解法, 执行用时: 146ms, 内存消耗: 5584K, 提交时间: 2020-01-13 20:04:50

#include<bits/stdc++.h>
using namespace std;
const int mx=100100;
int vis[mx];
int m,n;
#define  pa pair<int,int>
vector<pa>ve[mx];
int dis[mx];

int bfs(int X)
{
    priority_queue<int>q;
    q.push(X);
    for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;
    dis[1]=0; 
    vis[X]=1;
    while (!q.empty())
    {
        int x=q.top();
        q.pop();
        for(int i=0;i<ve[x].size();i++)
        {
            int v=ve[x][i].first;
            int w=ve[x][i].second;
            if(dis[x]+w<dis[v]&&vis[v]==0)
            {
                dis[v]=dis[x]+w;
                q.push(v);
            }
        }
    }
    return dis[n];
}

int main()
{
    cin>>n>>m;
    for(int i=0,x,y,s;i<m;i++)
    {
        cin>>x>>y>>s;
        ve[x].push_back({y,s});
        ve[y].push_back({x,s});
    }
    cout<<bfs(1)<<'\n';
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 264ms, 内存消耗: 5920K, 提交时间: 2023-08-02 17:43:38

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,now,a[N],v[N],w[N],nex[N],vis[N],head[N];
void addedges(int x,int y,int z){
	nex[++now]=head[x],w[now]=z;
	head[x]=now,v[now]=y;
}
queue<int>que;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		addedges(x,y,z),addedges(y,x,z);
	}
	memset(a,23,sizeof(a));
	que.push(1),a[1]=0;
	while(!que.empty()){
		int x=que.front();
		que.pop(),vis[x]=0;
		for(int i=head[x];i;i=nex[i])
			if(a[x]+w[i]<a[v[i]]){
				a[v[i]]=a[x]+w[i];
				if(!vis[v[i]])	que.push(v[i]),vis[v[i]]=1;
			}
	}
	cout<<a[n]<<endl;
	return 0;
}