首页 > [JSOI2015]地铁线路
开通博客写题解
头像 hnust_yangyanjun
发表于 2021-04-21 00:20:09
题意：有n个站点，m条路线，每条路线使用一次要交1块钱，给出每条路线的信息，从一个站点到下一个站点的时间为1，让你求从一个站点到另一个站点的最小花费是多少，此时花费时间最大为多少？ 思路：最短路+拓扑+dp一看就是图论题，第一问求最小花费，如何用最短路求呢，对于每一条路线我们要创建两个虚点，一个虚点 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-04-14 19:23:55
Solution 交汇地铁类型的图，一般都考虑分层建图或者借助额外的点建图。我们把起始的站点用表保留编号，上下地铁的位置建立额外的编号，这样就可以保证我们每次上下地铁计算到正确的票价。 所以我们再把地铁路线上的点拆分成向左向右两边的点，那么很明显边权存在两个(票价，时间)，那么从起始站点上地铁我们开 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 jzdx（hjh）
发表于 2021-04-22 11:55:20
题号 NC20214名称 [JSOI2015]地铁线路来源 [JSOI2015] 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld题目描述 JSOI王国的地铁又涨价了！正在JSOI旅游的JYY非常不开 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”