洛谷P 986[USACO 10 MAR]偉大な乳牛が集まるグリアCow Gat…
4013 ワード
テーマの説明
Bessie is planing the annual Greet Cow Gathering for cows all acros the country and、of course、she would like to chose the most convent location for the gathe ring to Tale place.
Each cow lives in one of N(1<=N==100,000)ディfferent barns(convently numberred 1.N)which are connected by N-1 roads in such a way that it is possible to get from any barn to any ther.Rorna.Rocker.Rockarch a.Rorn.i and B_i(1<=Auui<=N;1<=Buui<=N)and has length L_i(1<=Luui<=1,000).The Great Cow Gathering can be held at any one of these N barns.Moreover,barn i has C_i(0<=Cui<=1,000)cows living in it.
When chosing the barn in which to hold the Cow Gathering,Bessie wishes to maximize the convevevensience(which is to say minimize the inconveveveventience)of the inconsen location.The inconvevevevevevevevenience of chosing barning barn the(i.e.if the distance from barn i to barn X is 20,then the travel distance is Cui*20).Help Bessie chose the most convent location for the Gret Cow
ギャザリング.
Consder a country with five barns with[various capacities]connected by various roads of varying lengths.In this set of barns,neither barn 3 nor barn 4 housses any cows.
1 3 4 5
@-------1-@-3-3--@[2]
[1]124
2(124)@[1]2 Bessie can Hold the Gathe the thering in any of five barns;here is the table of inconventiences callted for each possible location:
Gather-----Inconvenience------
Location B 1 B 2 B 3 B 4 B 5 Total
1 0 3 0 14 17
2 3 0 0 0 0 16 19
3 1 2 0 0 12 15
4 4 5 0 0 6 15
5 7 8 0 0 0 15
If Bessie Holds the gathe ring in barn 1,then the inconvenience from each barn are:
Barn 1 0--no travl time there!
Barn 2 3--total travl distance is 2+1=3 x 1 cow=3 Barn 3 0--no cows there!
バーン4 0--no cows there!
Barn 5 14--total travl distance is 3+3+1=7 x 2 cows=14 So the total inconventience is 17.
The best possible conventience 15、achievble able at by holding the Gathe Gathering at barns 3、4、or 5.
Bessieは年に一度の乳牛大集会を計画しています.全国から来た乳牛は将来この集会に参加します.もちろん、一番便利な場所を選んでこの集会を開催します.
各乳牛はN(＝N(=100,000)の農場の一つで、これらの農場はN-1の道路で接続され、どの農場からも別の農場に到達することができます.道路iは農場のAuuiとBuui(1)<=Auui<=N;1==Buui<=N)を接続し、長さはLui(1==Lui=1)の農場で別のハウスに住むことができます.(0<=Cui<=1,000)乳牛のみです.
集会の場所を選ぶ時、Bessieは最も便利な程度を望んでいます.例えば、第X農場を集会場所として選んでいます.その不便さは他の牛小屋の中で乳牛ごとに集会に参加するための道の和です.Bessieが一番便利な場所を見つけて大集会をするように手伝ってくれます.
入出力フォーマット
入力フォーマット: Line 1:A single integer:N Lines.N＋1:Line i＋1 contains a single integer:Cui Lines N+2..2*N:Line i+N+1 contains three integers:Aui、Bui、and Luui 出力フォーマット: Line 1:The minimum inconventience possible 入出力の例
サンプル例を入力します
Bessie is planing the annual Greet Cow Gathering for cows all acros the country and、of course、she would like to chose the most convent location for the gathe ring to Tale place.
Each cow lives in one of N(1<=N==100,000)ディfferent barns(convently numberred 1.N)which are connected by N-1 roads in such a way that it is possible to get from any barn to any ther.Rorna.Rocker.Rockarch a.Rorn.i and B_i(1<=Auui<=N;1<=Buui<=N)and has length L_i(1<=Luui<=1,000).The Great Cow Gathering can be held at any one of these N barns.Moreover,barn i has C_i(0<=Cui<=1,000)cows living in it.
When chosing the barn in which to hold the Cow Gathering,Bessie wishes to maximize the convevevensience(which is to say minimize the inconveveveventience)of the inconsen location.The inconvevevevevevevevenience of chosing barning barn the(i.e.if the distance from barn i to barn X is 20,then the travel distance is Cui*20).Help Bessie chose the most convent location for the Gret Cow
ギャザリング.
Consder a country with five barns with[various capacities]connected by various roads of varying lengths.In this set of barns,neither barn 3 nor barn 4 housses any cows.
1 3 4 5
@-------1-@-3-3--@[2]
[1]124
2(124)@[1]2 Bessie can Hold the Gathe the thering in any of five barns;here is the table of inconventiences callted for each possible location:
Gather-----Inconvenience------
Location B 1 B 2 B 3 B 4 B 5 Total
1 0 3 0 14 17
2 3 0 0 0 0 16 19
3 1 2 0 0 12 15
4 4 5 0 0 6 15
5 7 8 0 0 0 15
If Bessie Holds the gathe ring in barn 1,then the inconvenience from each barn are:
Barn 1 0--no travl time there!
Barn 2 3--total travl distance is 2+1=3 x 1 cow=3 Barn 3 0--no cows there!
バーン4 0--no cows there!
Barn 5 14--total travl distance is 3+3+1=7 x 2 cows=14 So the total inconventience is 17.
The best possible conventience 15、achievble able at by holding the Gathe Gathering at barns 3、4、or 5.
Bessieは年に一度の乳牛大集会を計画しています.全国から来た乳牛は将来この集会に参加します.もちろん、一番便利な場所を選んでこの集会を開催します.
各乳牛はN(＝N(=100,000)の農場の一つで、これらの農場はN-1の道路で接続され、どの農場からも別の農場に到達することができます.道路iは農場のAuuiとBuui(1)<=Auui<=N;1==Buui<=N)を接続し、長さはLui(1==Lui=1)の農場で別のハウスに住むことができます.(0<=Cui<=1,000)乳牛のみです.
集会の場所を選ぶ時、Bessieは最も便利な程度を望んでいます.例えば、第X農場を集会場所として選んでいます.その不便さは他の牛小屋の中で乳牛ごとに集会に参加するための道の和です.Bessieが一番便利な場所を見つけて大集会をするように手伝ってくれます.
入出力フォーマット
入力フォーマット:
サンプル例を入力します
5
1
1
0
0
2
1 3 1
2 3 2
3 4 3
4 5 3
15
#include
#include
#include
using namespace std;
const int N=100005;
int n,cnt,hd[N];
long long ans=LLONG_MAX,c[N],s1[N],s2[N],ans1[N],ans2[N];
struct edge
{
int nxt,to;
long long val;
}v[2*N];
void addedge(int x,int y,int z)
{
++cnt;
v[cnt].to=y;
v[cnt].val=z;
v[cnt].nxt=hd[x];
hd[x]=cnt;
}
void dfs(int u,int fa)
{
s1[u]+=c[u];
for(int i=hd[u];i;i=v[i].nxt)
if(v[i].to!=fa)
{
dfs(v[i].to,u);
ans1[u]+=ans1[v[i].to]+s1[v[i].to]*v[i].val;
s1[u]+=s1[v[i].to];
}
}
void dfss(int u,int fa)
{
s2[u]+=c[u];
for(int i=hd[u];i;i=v[i].nxt)
if(v[i].to!=fa)
{
s2[v[i].to]+=s2[u]+s1[u]-s1[v[i].to]-c[u];
ans2[v[i].to]+=ans2[u]+ans1[u]-ans1[v[i].to]-s1[v[i].to]*v[i].val+(s1[u]+s2[u]-s1[v[i].to]-c[u])*v[i].val;
dfss(v[i].to,u);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=n-1;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,z);
}
dfs(1,0);
dfss(1,0);
for(int i=1;i<=n;i++)
ans=min(ans,ans1[i]+ans2[i]);
printf("%lld
",ans);
return 0;
}