dp+spfa在NOIP2009提高组中的最优贸易

[NOIP2009 提高组] 最优贸易

题目描述

国家C拥有n座大城市以及m条道路。每条道路都连接着这n个城市中的两个。任意两个城市之间至多有一条直接相连的道路。在这些m条道路上，一部分是单向行驶的道路，另一部分是双向行驶的道路，在统计数量时每一条双向道路都被算作一条。

国家C广袤无垠。各地资源分布状况各有特色。这就直接造成了同一种商品在不同城市价格各有差异。然而，在同一个城市的同一市场中买进与卖出价格都是固定的

商人阿龙来到C国进行游历。当他得知同一商品在不同城市的售价可能存在差异后,于是决定，在游历过程中通过在同一城市购买商品并在另一城市出售的方式赚取旅费。设C国有n个城镇,其标号依次为1至n,阿龙计划从1号城镇启程,并最终选择抵达n号城镇作为目的地。根据旅行规划,同一城镇可多次访问而不必遍历所有城镇。为了赚取旅费的目的,他在行程中会选择某一城镇购入他最喜爱的商品——水晶球,并将此物随后售出于另一城镇中获得差价收益。鉴于他此次出访的主要目的是游览文化与品尝美食

基于假设 C 国有大都市区数量共计 5 个，在城市标识与交通网络布局图中以图示形式呈现各城市间的交通联系方式。其中通过单向箭头表示对应的道路属于单向通行方向路径配置方式设计；而采用双向箭头则代表该条道路被规划为双向通行的道路结构特征设置方案。

![](https://cdl.itadn.