先从起点终点分别跑最短路，求出所有在最短路上的边以及必经边。必经边也就是在拓扑序上不和其他（在最短路上的）边相交的边。翻转在最短路上的边显然不会使得最短路变短，因此如果翻转的是最短路上的必经边那么最短路变长，否则不变。对于其他边，判断一下翻转后经过这条边是否优于原来的最短路即可。
QOJ.ac
QOJ
Discussion #304 for Problem #3287. Pizza Delivery
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:00:16
Last updated: 2025-12-14 07:00:19
题解
Comments
No comments yet.