Dijkstra算法

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int vis[N]; //
int dis[N]; //存储点s与其他点的距离 
int n,m,s;
struct node{
	int v,w;
	bool operator <(const node &x)const{
		return x.w<w;
	} //重定向 小于号把priority_queue变成小根堆 
}; //存储最短路
vector<node> g[N]; //存距离
priority_queue<node> q; //优先队列默认大根堆
void dij(){
	dis[s]=0; //自己为0
	vis[s]=1; //
	q.push(node{s,0}); //存入s本身
	while(!q.empty()){
		node t=q.top();
		q.pop();
		int now=t.v;
		vis[now]=0;
		for(int i=0;i<g[now].size();i++){
			int v=g[now][i].v;
			if(dis[v]>dis[now]+g[now][i].w){
				dis[v]=dis[now]+g[now][i].w;
				if(vis[v]==0){
					q.push(node{v,dis[v]});
					vis[v]=1;
				}
			}
		}
	}
}
int main(){	
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		dis[i]=inf;  //存为inf
	}
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(node{v,w}); //存储权值
	}
	dij(); //Dijkstra
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
 	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,u,v,w;
long long ans;
struct node{
    int x;
    long long dis;
    node(int X, long long DIS) :  x(X),dis(DIS){} //这是什么意思呢
    bool operator >(const node&o) const{return dis>o.dis;}
};
int inf=INT_MAX;
int ver[N],wei[N],nex[N],head[N],tot; //依次存储v w 下一个点 计数
priority_queue<node,vector<node>,greater<node> > q;
long long dis[N];
void addedge(int u, int v, int w){ //建边
    ver[tot]=v,wei[tot]=w,nex[tot]=head[u],head[u]=tot++;
}
void dij(int s){
    for(int i=1;i<=n<<1;++i) dis[i]=inf;
    dis[s]=0;
    q.push(node(s,0));
    while(!q.empty()){
        node cur=q.top();
		q.pop();
        if(dis[cur.x]<cur.dis) continue;
        for(int i=head[cur.x];~i;i=nex[i]){
            if(dis[ver[i]]>cur.dis+wei[i]) {
                dis[ver[i]]=cur.dis+wei[i];
                q.push(node(ver[i],dis[ver[i]]));
            }
        }
    }
}
int main(){    
	memset(head,-1,sizeof(head));
    cin>>n>>m;
    for(int i=1;i<=m+1;i++){
        cin>>u>>v>>w;
		addedge(u,v,w);
		addedge(v+n,u+n,w); //反向
    }
	dij(1);
    for(int i=2;i<=n;++i) ans+=dis[i];
    dij(1+n);
    for(int i=2+n;i<=n<<1;++i) ans+=dis[i];
    cout<<ans<<endl;
    return 0;
}