原题目

题目描述
给定一个 \(n\) 个点，\(m\) 条有向边的带非负权图，请你计算从 \(s\) 出发，到每个点的距离。

数据保证能从 \(s\) 出发到任意点。

输入格式
第一行为三个正整数 \(n, m, s\)。 第二行起 \(m\) 行，每行三个非负整数 \(u_i, v_i, w_i\)，表示从 \(u_i\) 到 \(v_i\) 有一条权值为 \(w_i\) 的有向边。

输出格式
输出一行 \(n\) 个空格分隔的非负整数，表示 \(s\) 到每个点的距离。

初次尝试：

由于刚刚学过数据结构，很快就有了思路（采用邻接表存储+\(Dijkstra\)算法），但是由于从没实践过??,所以写的时候有点费劲，又调试了好久，才得到正确的结果：

• 第一代代码：

//单源最短路传统
#include
using namespace std;
int dist[100005],path[100005];
bool S[100005];
typedef struct e{
	int key;
	int d;
	struct e *next;
}edge;
typedef struct{
	edge *out=NULL;
}node;
void add(node *n,int v,int w)
{
	edge *e=(edge *)malloc(sizeof(edge));
	e->key=v;
	e->d=w;
	e->next=n->out;
	n->out=e;
}
void kl(node *n,int k)
{
	edge *e=n->out;
	while(e!=NULL)
	{
		if(e->d+dist[k]key])
		{
			dist[e->key]=e->d+dist[k];
			path[e->key]=k;
		}
		e=e->next;
	}
}
int main()
{
	memset(dist,100,sizeof(dist));//距离初始化为无穷，这里为一个很大的数
	memset(path,-1,sizeof(path));
	int n,m,s,u,v,w;	
	node N[100005];
	scanf("%d%d%d",&n,&m,&s);
	int nn=n;
	dist[s]=0;path[s]=s;dist[0]=2000000005;
	for(int i=0;i

//单源最短路堆优化
#include
using namespace std;
int dist[100005];//int path[100005];//本题path[]数组好像没什么用 
bool vis[100005];
//定义数据结构
struct edge{
	int key;
	int d;
	edge *next;
};
struct node{
	edge *out=NULL;
}N[100005];
struct node_dist{
	int dist;
	int node;
	bool operator < (const node_dist &x)const
	{
		return dist>x.dist; 
	}//重载运算符使兼容，并定义成小根堆
};
std::priority_queue q;//使用stl库定义一个优先队列
//定义函数
void add(node *n,int v,int w)
{
	edge *e=(edge *)malloc(sizeof(edge));
	e->key=v;
	e->d=w;
	e->next=n->out;
	n->out=e;
}

void kaolv(node *n,int k)
{
	edge *e=n->out;
	while(e!=NULL)
	{
		if(e->d+dist[k]key])
		{
			dist[e->key]=e->d+dist[k];
//			path[e->key]=k;
			q.push({dist[e->key],e->key});
		}
		e=e->next;
	}
}

int main()
{
	int n,m,s,u,v,w; 
	memset(dist,100,sizeof(dist));//将dist[]数组所有元素初始化为无穷（很大的值)
//	memset(path,-1,sizeof(path));	
	scanf("%d %d %d",&n,&m,&s);
	int nn=n;
	//输入 
	for(int i=0;i