[C++知识库]迪杰斯特拉算法堆优化机试模板|C++|P4779 【模板】单源最短路径（标准版）

前面发过Dijkstra的堆优化的模板，但是用这个模板会超时，其实TLE超时，就要想着剪枝，然后我在循环里

//Dijkstra堆优化
//Edge:记录去向和长度（int to,int length）
//Point:记录Number 和长度

#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#pragma warning(disable:4996);

const int maxn = 100010;
const int INF = 0x3f3f3f3f;
//n个点、m条边、s是起点
int n, m, s;
int dis[maxn];

struct Point
{
	int number; //第几号结点
	int dis; //到原点的距离
	Point(int number, int l) :number(number), dis(l) {}
	bool operator< (const Point& P) const {
		return dis > P.dis;
	}
};

struct Edge
{
	int to;
	int length;
	Edge(int t, int l) :to(t), length(l) {}
};
vector<Edge> Adj[maxn];
bool vis[maxn];

void dijkstra(int s)
{
	dis[s] = 0;
	priority_queue<Point> q;
	q.push(Point(s, dis[s]));
	while (!q.empty()) {
		Point P_temp = q.top();
		q.pop();
		int u = P_temp.number;
		if(vis[u] == true)
		    continue;
		vis[u] = true;
		for (int i = 0; i < Adj[u].size(); i++)
		{
			int end = Adj[u][i].to;
			if (vis[end] == false && dis[end] > Adj[u][i].length + dis[u])
			{
				dis[end] = Adj[u][i].length + dis[u];
				q.push(Point(end, dis[end]));
			}
		}
	}
}

int main()
{
	scanf("%d %d %d", &n, &m, &s);
	//记录m条边
	for (int i = 0; i < m; i++) {
		int from, to, distance;
		scanf("%d %d %d", &from, &to, &distance);
		Adj[from].push_back(Edge(to, distance));
		//Adj[to].push_back(Edge(from, distance));
	}
	fill(dis, dis + n + 1, INF);
	fill(vis, vis + n + 1, false);
	dijkstra(s);
	for (int i = 1; i <= n; i++)
	{
		printf("%d ", dis[i]);
	}
}