[Acwing] 853.有边数限制的最短路 Bellman-Frod的性质应用

前言

这题算是一个性质应用了 : (具体证明好像没说) 既然Bellman-ford可以做,为什么不试试 spfa呢 传送门:

Bellman-Frod 基本思路

1. 迭代 n n n 次
2. 对于每次迭代,我们都对所有边进行松弛操作

代码大致如下 :

for(int i=1;im>>k;

	while(m -- )
	{
		int a,b,c;
		cin>>a>>b>>c;
		g[a].push_back({b,c});
	}
	
	bellman_ford();
	
	if(dist[n] > INF/2 )
	cout