Skip to content

11267: 【原1267】线路铺设

题目

题目描述

author: syj, Cheezer 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1267

Description

经过台长CC的不懈努力,艰苦奋斗,CCTV已经成长壮大为国际大电视台了。最近,

CCTV刚刚打入D国市场,CC打算将CCTV的信号传至D国的n个城市中,每个城市的人数为wi,但由于D国内没有CCTV的相关线路,所以现在CC需要铺设一些线路来将信号传输至这n个城市。

由于城市之间的地理状况不尽相同,所以铺设费用也有所不同。CCTV设在D国的总信号站处于1号城市,即信号源是1号城市,除1号城市外的所有城市的信号需要由一些线路从总信号站传输过来。CC经过综合分析评估,设计了m条备选线路,每条路线包含3个信息:ai,bi,ci,表示这条线路中由ai城市向bi城市传输信号的单位费用为ci。每条线路的负荷量为信号需要经过这条线路的城市的人数和,铺设一条线路的最终费用这条线路的(单位费用)*(负荷量),总的铺设费用为所有线路的费用之和。CC希望每个城市都能接收到信号,同时他也希望总的铺设费用最少,你需要求出这个最少的铺设费用。如果不存在一个方案能使每个城市都接收到信号,输出“No Answer”(不含引号)。

Input Format

第一行为n,m,含义见描述。

接下来一行包含n个数,表示第i个城市的人数。

接下来m行,每行三个数ai,bi,ci含义见描述。

对于30%的数据,n<=100,m<=10000。

对于100%的数据,n<=50000,m<=100000。

∑w[i]、∑c[i]不超过maxlongint , 可能存在两个城市之间有多条备选线路。

Output Format

如果存在方案使每个城市都接收到信号,则输出最小的总铺设费用,否则输出“No Answer”(不含引号)

如果存在方案,最小的总铺设费用在long long范围内。

Sample Input

3 2
1 1 2
1 2 15
2 3 1

Sample Output

47

Sample Input

3 2
10 5 3
1 2 1
3 2 2

Sample Output

No Answer

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!