先从起点终点分别跑最短路，求出所有在最短路上的边以及必经边。必经边也就是在拓扑序上不和其他（在最短路上的）边相交的边。翻转在最短路上的边显然不会使得最短路变短，因此如果翻转的是最短路上的必经边那么最短路变长，否则不变。对于其他边，判断一下翻转后经过这条边是否优于原来的最短路即可。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
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.