网站建设的市场策划,拼多多网站建设,百度多久收录网站,东营出租房屋信息网题目描述 Description Abstinence#xff08;戒酒#xff09;岛的居民们酷爱一种无酒精啤酒。以前这种啤酒都是从波兰进口#xff0c;但今年居民们想建一个自己的啤酒厂。岛上所有的城市都坐落在海边#xff0c;并且由一条沿海岸线的环岛高速路连接。酒厂的投资者收集了关于…题目描述 Description Abstinence戒酒岛的居民们酷爱一种无酒精啤酒。以前这种啤酒都是从波兰进口但今年居民们想建一个自己的啤酒厂。岛上所有的城市都坐落在海边并且由一条沿海岸线的环岛高速路连接。酒厂的投资者收集了关于啤酒需求量的信息即每天各城市消费的啤酒桶数。另外还知道相邻城市之间的距离。每桶啤酒每英里的运费是1元。日运费是将所需要的啤酒从酒厂运到所有城市所必需的运费之和。日运费的多少和酒厂的选址有关。投资者想找到一个合适的城市来修建酒厂以使得日运费最小。 请设计一个程序从文件bre.in 读入城市的数目、相邻两城市间的距离以及每个城市消费的啤酒桶数计算最小的日运费将结果写到输出文件bre.out中。 输入描述 Input Description 第一行是一个整数n5 n 10000 表示城市的数目。 城市沿高速路编号使得相邻的城市的编号也相邻城市1和n也被认为是相邻。 以下的n行每行有两个非负整数。第I1行的数 zi、di分别是城市I每日的啤酒消费量桶和从城市I沿高速路到下一个城市的距离英里。高速路的总长不会超过65535 英里。每座城市的日消费量不会超过255桶。 输出描述 Output Description 一个整数表示所需的最小日运费元。 样例输入 Sample Input 6 1 2 2 3 1 2 5 2 1 10 2 3 样例输出 Sample Output 41 /*第一次做INF开小了数据也没用long long得了45分。
*/
#includecstdio
#includeiostream
#define M 10010
#define LL long long
#define INF 9223372036854775807LL
using namespace std;
int dis[M],a[M],sum,n;
LL mon[M];
int main()
{scanf(%d,n);for(int i1;in;i){int x;scanf(%d%d,a[i],x);if(i!n)dis[i1](xdis[i]);sumx;}for(int i1;in;i)for(int ji1;jn;j){int pdis[j]-dis[i];mon[i](LL)(min(p,sum-p)*a[j]);mon[j](LL)(min(p,sum-p)*a[i]);}LL ansINF;for(int i1;in;i)if(mon[i]ans)ansmon[i];printf(%lld,ans);return 0;
} View Code 转载于:https://www.cnblogs.com/harden/p/5655878.html
