真身败名裂了。 A #include<bits/stdc++.h> using namespace std; #define ll long long #define uint unsigned long long #define PII pair<int,int> #define MP make_pair #define …

图论这一块内容比较多，而且题目涉及的 Trick 也很多，因此分若干篇。 本文略去所有算法本身性质的证明过程。 最短路 Dijkstra和SPFA $\text{Dijkstra}$ 算法基于一个重要的性质：全局最小值不可能再被任何边更新。这样，在边权为非负数的最短路问题中显然满足，在存在负边时不满足。同时，保证了最多从每个节点处扩展 $1$ 次，…