WA #10

#include<bits/stdc++.h>
#define ll long long
#define set1(H) for(int i=0;i<=n;i++) a[i]=H;
using namespace std;
vector<pair<ll,ll> > vi[300005];
ll a[300005];
map<ll,ll> b;
ll n,m,s;
set<pair<ll,ll>> st;
ll INF=1e18;
ll find(){
	pair<ll,ll> g=*st.begin();
	return g.second;
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	cin>>n>>m;
	set1(INF);
	for(int i=0;i<m;i++){
		ll u,v,w;
		cin>>u>>v>>w;
		vi[u].push_back(pair<ll,ll>(v,w));
	}
	a[1]=0;
	st.insert(pair<ll,ll>(0,1));
	ll u=0;
	while(!st.empty()){
		u=find();
		if(b[u]>=1){
			st.erase(st.begin());
			continue;
		}
		b[u]=1;
		for(int i=0;i<vi[u].size();i++){
			ll o=vi[u][i].second;
			ll p=vi[u][i].first;
			if(a[u]+o<a[p]){
				a[p]=a[u]+o;
				st.insert(pair<ll,ll>(a[p],p));
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]==INF){
			cout<<-1ll<<' ';
			continue;
		}
		cout<<a[i]<<' ';
	}
	return 0;
}

提交记录