Mn Zn 95pts求助

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 2e5 + 10;
typedef pair<int,int> pii;
int n,m,dist[N],sum[N];
int d1[N],d2[N];
vector<pair<int,int>> g[N],f[N];

inline void solve()
{
	queue<int> q;
	for(int i = 1;i <= n;i++)
		if(d1[i] == 0)
			q.push(i);
	
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		
		for(auto [v,w] : g[u])
		{
			dist[v] = max(dist[v],dist[u] + 1);
			d1[v]--;
			if(d1[v] == 0)
				q.push(v);
		}
	}
	
	while(q.size()) q.pop();
	for(int i = 1;i <= n;i++)
		if(d2[i] == 0)
			q.push(i);
	
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		int minx = 2e18,rec = 0;
		sum[rec] = 2e18;
		
		for(auto [v,w] : f[u])
			if(minx >= w && dist[v] == dist[u] - 1)
			{
				if(sum[v] < sum[rec] || minx > w) 
					rec = v;
				minx = w;
			}
		
		if(f[u].empty()) minx = 0;
		if(rec == 0) sum[u] = minx;
		else sum[u] = sum[rec] + minx;
		
		for(auto [v,w] : g[u])
			if(--d2[v] == 0)
				q.push(v);
	}
	return ;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;

	for(int i = 1;i <= m;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		g[v].push_back({u,w});
		f[u].push_back({v,w});
		d1[u]++;d2[u]++;
	}
	
	solve();
	
	for(int i = 1;i <= n;i++)
		cout << dist[i] << " " << sum[i] << endl;
	return 0;
}