Dijkstra 堆优化

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
const ll INF = 1e18;
vector<pair<int, int> >g[N];
int t[N], p[N], n, m;
ll dis[N];
bool tag[N];
struct node
{
	int id;
	ll w;
	friend bool operator < (const node &n1, const node &n2)
	{
		return n1.w > n2.w;
	}	
};
priority_queue<node>q;
inline void Dijkstra(int s)
{
	for(int i = 1;i <= n;++i)
	{
		if(i != s) dis[i] = INF;
		else dis[i] = 0;
		t[i] = 0;
		q.push((node){i, dis[i]});
	}
	p[s] = s; 
	int cnt = 0;
	while(cnt < n)
	{
		node cur;
		while(q.size())
		{
			cur = q.top();
			q.pop();
			if(cur.w == dis[cur.id] && !tag[cur.id])
				break;	
		}	
		tag[cur.id] = 1;
		cnt++;
		for(auto v : g[cur.id])
		{
			if(!tag[v.first])
			{
				if(dis[v.first] > dis[cur.id]+v.second+t[cur.id])
				{
					dis[v.first] = dis[cur.id]+v.second+t[cur.id];
					p[v.first] = cur.id;
					t[v.first] = t[cur.id]+1;
					q.push((node){v.first, dis[v.first]});
				}
			}
		} 
	} 
}
inline void print(int u)
{
	if(u == 1)
	{
		cout << "1 ";
		return;
	}
	print(p[u]);
	cout << u << " ";
}
int main()
{
	int u, v, w;
	cin >> n >> m;
	while(m--)
	{
		scanf("%d%d%d", &u, &v, &w);
		g[u].push_back(make_pair(v, w));
	}
	Dijkstra(1);
	if(dis[n] >= INF)
	{
		cout << -1;
		return 0;
	}
	cout << dis[n] << "\n";
	print(n);
	return 0;	
}