题目传送门前置知识线段树优化建图|最短路解法考虑对票建虚点，从\(c_{i}\)向\(i+n\)连一条权值为\(p_{i}\)的边，然后从\(i+n\)向\([a_{i},b_{i}]\)连一条权值为\(0\)的边。建出反图后\(1\toi\)和\(n\toi\)的路径集合会有重复统计的部分，不妨以\(dis_{1,i

[USACO21DEC]TicketsP首先我们思考暴力的\(O(n^2)\)怎么做。显然比起每次以\(i\)为起点跑\(n\)遍最短路，建反图后分别以\(1\)和\(n\)为起点跑两遍最短路是更加经济的方式。然后你可能会以为\(\text{dis}(1,i)+\text{dis}(n,i)\)就是答案了，之后你就会发现连样例都过