帮帮萌新吧

本题WA链接

标准版AC链接

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1000010;
const int maxm = 1000010;
const int inf = 0x7fffffff;
struct node
{
	int to,data,next;
}e[maxm];
struct tree
{
	int id,data;
}t[maxn];
int head[maxn],tot = 0;

int n,m,s;
bool vis[maxn];
int f[maxn];
int sum = 0;

void add(int x , int y , int z)
{
	e[++tot].data = z;
	e[tot].to = y;
	e[tot].next = head[x];
	head[x] = tot;
}

inline void check(int i)
{
	int son1 = i * 2 , son2 = i * 2 + 1;
	if(son1 > sum)
		return;
	if(son2 <= sum && t[i].data > t[son1].data && t[i].data > t[son2].data)
	{
		if(t[son1].data < t[son2].data)
		{
			swap(t[i] , t[son1]);
			check(son1);
		}
		else
		{
			swap(t[i] , t[son2]);
			check(son2);
		}
	}
	else
	{
		if(t[i].data > t[son1].data)
		{
			swap(t[i] , t[son1]);
			check(son1);
		}
		if(son2 <= sum && t[i].data > t[son2].data)
		{
			swap(t[i] , t[son2]);
			check(son2);
		}
	}
}
inline void build(int i)
{
	if(i == 1) return;
	if(t[i / 2].data > t[i].data)
	{
		swap(t[i / 2] , t[i]);
		build(i / 2);
	}
}
inline void ad(int x , int id)
{
	t[++sum].data = x;
	t[sum].id = id;
	build(sum);
}
void del()
{
	swap(t[1] , t[sum]);
	sum --;
	check(1);
}
int main()
{
	scanf("%d%d%d", &n,&m,&s);
	for(int i = 1 ; i <= m ; i ++)
	{
		int x,y,z;
		scanf("%d%d%d", &x,&y,&z);
		add(x , y , z);
	}
	for(int i = 1 ; i <= n ; i ++)
		f[i] = inf;
	for(int i = head[s] ; i ; i = e[i].next)
	{
		f[e[i].to] = min(e[i].data , f[e[i].to]);
	}
	for(int i = 1 ; i <= n ; i ++)
		if(f[i] != inf)
			ad(f[i] , i);
	f[s] = 0;
	int id,data;
	vis[1] = 1;
	int total = 1; 
	for(int i = 1 ; 1 ; i ++)
	{
		id = t[1].id , data = t[1].data;
		del();
		if(vis[id] == 1)
			continue;
		if(total == n)
			break;
		for(int j = head[id] ; j ; j = e[j].next)
		{
			if(data + e[j].data < f[e[j].to])
			{
				f[e[j].to] = data + e[j].data;
				ad(f[e[j].to] , e[j].to);
			}
		}
		vis[id] = 1;
		total ++;
	}
	for(int i = 1 ; i <= n ; i ++)
	{
		if(f[i] == inf)
			cout<< 2147483647<<' ';
		else
			cout<<f[i]<<' ';
	}
}