P3317 【模板】单源最短路径

#include <bits/stdc++.h>
#include <queue> 
using namespace std;
int n, m, s;
struct NodePath{
	int net;//边 -> 边   这条边的出发点上出发的上一条边的编号 
	int v;//边 -> 点  这条边的终点编号 
	int w;//边 -> 值  这条边的权值 
} ph[500000 + 9];
struct NodePoint{
	int head;//点 -> 边   从这个点出来的最新的一条边的编号 
	long long dis;//到每个点的最短距离 
//	NodePoint():head(0), dis(0x3f3f3f3f){}
	NodePoint(int a = 0, long long b = 0x3f3f3f3f)//初始无穷大 
	{
		head = a;
		dis = b;
	}
} pt[100000 + 9];
typedef pair <long long, int> point;//第一项是到点的最短路，第二项是该点的编号 
void node(int x, int y, int ww, int e);//邻接表初始化 
priority_queue <point, vector<point>, greater<point> > q;
//优先队列，优先返回较小值 （默认先排 pair 的第一位） 
int main()
{
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++)
	{
		int x, y, ww;
		cin >> x >> y >> ww;
		node (x, y, ww, i);//邻接表 
	}
//	int inf = 0x3f3f3f3f;
//	fill(pt+1, pt+1+n, NodePoint(0,inf));
	pt[s].dis = 0;//到自己的距离为0 
	q.push(point(0,s));//源点入队 
	while (!q.empty())
	{
		point x = q.top();
		q.pop();
		if (x.first > pt[x.second].dis)//剪枝：没有继续找下去的必要 
			continue;
		for (int i = pt[x.second].head; i != 0; i = ph[i].net)//把这个点的每条出边跑一次 
		{
			int z = ph[i].v; //把终点记录 
			if (x.first + ph[i].w < pt[z].dis)//到 x 点的最短距离 + 该边权值 < 到 z 点的最短距离
			{
				pt[z].dis = x.first + ph[i].w;//收缩
				q.push(point(pt[z].dis, z));//将该点更新 
			} 
		} 
	}
	for (int i = 1; i <= n; i++)
		cout << pt[i].dis <<" ";
	cout << endl;
	return 0;  
}
void node(int x, int y, int ww, int e)//邻接表初始化 
{
	ph[e].net = pt[x].head;//指向该顶点的上一条边 
	pt[x].head = e;
	ph[e].v = y;
	ph[e].w = ww;
}

#include <bits/stdc++.h>
#include <queue>
using namespace std;
struct NodePath{//建边 
	int nex, v, w;
} ph[500000 + 9];
struct NodePoint{//建点 
	long long dis;
	int head; 
	NodePoint (int a = 0, long long b = 2147483647)//构造函数：dis 初始正无穷 
	{
		head = a;
		dis = b;
	}
} pt[100000 + 9];
void node (int u, int v, int w, int e);//邻接表 
void SPFA(int a);
int main()
{
	int n, m ,s;
	cin >> n >> m >> s;//n 点 ； m 边 ； 求点 s 到其余各点的最短路 
	for (int i = 1; i <= m; i++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		node (x, y, w, i);//邻接表 
	}
	SPFA(s);
	for (int i = 1; i <= n; i++)
		cout << pt[i].dis <<" ";
	cout << endl;
	return 0;  
}
void SPFA(int s)
{
	queue <int> q;
	bool inQueue [100000 + 9];
	memset (inQueue, false, sizeof(inQueue));
	pt[s].dis = 0;//源点到自身距离为0
	q.push(s); 
	inQueue[s] = true;//s 在队列中 
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		inQueue[u] = false;
		for (int i = pt[u].head; i; i = ph[i].nex)//枚举从 u 出的每一条边
		{
			int v = ph[i].v; //枚举可从 u 直接走到的每一个点 v
			int w = ph[i].w;
			if (pt[v].dis > pt[u].dis + w)
			{
				pt[v].dis = pt[u].dis + w;
				if (!inQueue[v])
				{
					inQueue[v] = true;
					q.push(v);
				}
			}	 
		} 
	}
}
void node (int u, int v, int w, int e)
{
	ph[e].nex = pt[u].head;
	pt[u].head = e;
	ph[e].v = v;
	ph[e].w = w;
}