题目传送门:P2136 拉近距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 在之前有写过spfa做的题《[NOIP2009]最优贸易(分层图论 + SPFA最长路) – ErikTse Runtime》,不过那道题比较复杂,本题是一道纯模板题。 思路 直接spfa,有几个点需要注意。 这里是单向图,根据题意,需要对d[1][N]和d[N][1]取小。 注意判环,方法是如果一 […]
题目传送门:P2136 拉近距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 在之前有写过spfa做的题《[NOIP2009]最优贸易(分层图论 + SPFA最长路) – ErikTse Runtime》,不过那道题比较复杂,本题是一道纯模板题。 思路 直接spfa,有几个点需要注意。 这里是单向图,根据题意,需要对d[1][N]和d[N][1]取小。 注意判环,方法是如果一 […]
传送门:[NOIP2009]最优贸易 (nowcoder.com) 传送门2:P1073 [NOIP2009 提高组] 最优贸易 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 本题思路比较多,有分层图论,还可以用Tarjan缩点 + DP,由于俺的水平不够,所以用分层图论吧。 之前也写过一篇分层图论的文章《[JLOI2011]飞行路线(dijkstra分层最短路) – Erik […]
Eriktse
18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。
COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.
Theme Kratos | Hosted In TENCENT CLOUD