P3371 【模板】单源最短路径（弱化版）

题目：P3371 【模板】单源最短路径（弱化版）

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

0 2 4 3

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
#define maxm 500010
#define inf 2147483647

int n,m,s;
struct node
{
    int ed,w;   
};
vector<struct node> g[maxn];
int d[maxn];
int vis[maxn]={0};

void Dijkstra(int s){
	for(int i=1;i<=n;i++) d[i]=inf;//初始化 
	for(int i=0;i<g[s].size();i++)//将图中与s的边的权值赋给d[i] ,d[i]表示s->i这条边的距离 
		d[g[s][i].ed]=min(g[s][i].w,d[g[s][i].ed]);
	d[s]=0;
	vis[s]=1;//标记 
	
	for(int i=1;i<=n-1;i++){
		int min1=inf,p=0;
		for(int j=1;j<=n;j++)//在所有未标记点中找到d值最小的节点p
			if(!vis[j]&&min1>d[j]){ min1=d[j]; p=j;} 
			
		vis[p]=1;//标记 
		for(int j=0;j<g[p].size();j++){//更新，s->i之间的最短距离 d[i]=min(d[p]+p->i,d[i])
	    	if(d[p]+g[p][j].w<d[g[p][j].ed]){
	    		d[g[p][j].ed]=d[p]+g[p][j].w;
			}
		}	
	}
}
int main(){
	std::ios::sync_with_stdio(false);
	
	cin>>n>>m>>s;
	int a;
	node e;
	for(int i=0;i<m;i++){
		cin>>a>>e.ed>>e.w;
		g[a].push_back(e);
	}
	Dijkstra(s);
	for(int i=1;i<=n;i++){
		cout<<d[i]<<" ";
	}
	cout<<endl;
	return 0;
}

优先队列优化Dijkstra：

#include<bits/stdc++.h>
using namespace std;
#define maxn 10001
#define maxm 500010
#define inf 2147483647


int n,m,s;
struct Edge{
	int from , to ,dist;//起点、终点、边长
	Edge(int u,int v,int d):from(u),to(v),dist(d) {}
};
vector<Edge> edge;
vector<int> g[maxn];//g[i]储存的是点i相连的边在edge中的位置
int d[maxn];//d[i] s->i的距离
int vis[maxn]={0};//标记
 
struct node
{
    int u,d;//
	bool operator < (const node& x) const{
		return x.d<d ;//定义小于号
	}
};//优先队列元素类型


void Dijkstra(){
    priority_queue< node > q;
    for(int i=1;i<=n;i++) d[i]=inf;//初始化 
    d[s]=0;
    q.push((node){s,0});//进队列终点s 路径长为0 
    
    while( !q.empty() ){
    	
    	node x=q.top(); q.pop();//取顶（优先队列内d最小）
    	int u=x.u;
    	if(vis[u]) continue;//队列为空 即为所有点都更新了 
    	vis[u] =1;//标记 
    	
    	for(int i=0;i<g[u].size();i++){//搜索u所有连边
    	
    		Edge e=edge[g[u][i]];//连边 
    		if(d[e.to]>d[u]+e.dist){
    			//cout<<e.to<<" "<<d[e.to]<<" "<<d[u]+e.dist<<endl;
    			d[e.to]=d[u]+e.dist;//松弛操作 
    			q.push((node){ e.to,d[e.to]});//把新遍历到的点加入队列中
			}
		}
	}
}
int main(){
    std::ios::sync_with_stdio(false);
    
    cin>>n>>m>>s;
    int from,to,dist;
    
    for(int i=0;i<m;i++){
        cin>>from>>to>>dist;
        edge.push_back(Edge(from,to,dist));
        g[from].push_back(edge.size()-1);//边u-v在edge中的位置 
    }
    /*for(int i=1;i<=n;i++){
    	cout<<i<<" ";
    	for(int j=0;j<g[i].size();j++){
    		cout<<edge[g[i][j]].to<<" ";
		}
		cout<<endl;
    }*/
    Dijkstra();
    for(int i=1;i<=n;i++){
        cout<<d[i]<<" ";
    }
    cout<<endl;
    return 0;
}