luogu3371 【模板】单源最短路径 dijkstra堆优化

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n, m, s, dis[10005], din, uu, vv, ww, hea[10005], cnt;

bool vis[10005];

struct Node{

	int idx, val;

}dui[1100005];

struct Edge{

	int too, nxt, val;

}edge[1000005];

bool cmp(Node x, Node y){

	return x.val>y.val;

}

void add_edge(int fro, int too, int val){

	edge[++cnt].nxt = hea[fro];

	edge[cnt].too = too;

	edge[cnt].val = val;

	hea[fro] = cnt;

}

int main(){

	cin>>n>>m>>s;

	for(int i=1; i<=m; i++){

		scanf("%d %d %d", &uu, &vv, &ww);

		add_edge(uu, vv, ww);

	}

	memset(dis, 0x3f, sizeof(dis));

	dis[s] = 0;

	dui[++din] = (Node){s, 0};

	while(din){

		Node x=dui[1];

		pop_heap(dui+1, dui+1+din, cmp);

		din--;

		if(vis[x.idx])	continue;

		vis[x.idx] = true;

		for(int i=hea[x.idx]; i; i=edge[i].nxt){

			int t=edge[i].too;

			if(!vis[t] && dis[t]>dis[x.idx]+edge[i].val){

				dis[t] = dis[x.idx] + edge[i].val;

				dui[++din] = (Node){t, dis[t]};

				push_heap(dui+1, dui+1+din, cmp);

			}

		}

	}

	for(int i=1; i<=n; i++)

		if(dis[i]==0x3f3f3f3f)	printf("2147483647 ");

		else	printf("%d ", dis[i]);

	printf("\n");

	return 0;

}