传送门：[NOIP2009]最优贸易 (nowcoder.com) 传送门2：P1073 [NOIP2009 提高组] 最优贸易 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 本题思路比较多，有分层图论，还可以用Tarjan缩点 + DP，由于俺的水平不够，所以用分层图论吧。 之前也写过一篇分层图论的文章《[JLOI2011]飞行路线（dijkstra分层最短路） – Erik […]

题目链接：K-[JLOI2011]飞行路线_WUT2021校内训练⑦ (nowcoder.com) 题意请看原题，是中文的。 思路 本题突破口在K <= 10，且N <= 1e4。 设起点s, 终点t。 一般的最短路的题目都是建立一个二维图，这里我们建立一个K层的三维图，从第 0 层开始，第 i 层表示用了 i 次免费航线。这样最后统计所有t + N * i(0 <= i < […]

题目链接：https://ac.nowcoder.com/acm/contest/28848/A 题目大意 企鹅国中有N座城市，编号从1到N。对于任意的两座城市i和j，企鹅们可以花费(i xor j) * C （xor表示异或）的时间从城市i走到城市j，这里C为一个给定的常数。当然除此之外还有M条单向的快捷通道，第i条快捷通道从第Fi个城市通向第Ti个城市，走这条通道需要消耗Vi的时间。现在来自P […]