TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1261
  • 問題
  • P1261灌水
    制限 : 時間制限 : 1000 MS   メモリ制限 : 65536 KB
    問題説明

    Farmer John决定给他分别用1到N(1 <= N <= 300)分别编号的牧草浇水,他可以直接在一颗牧草旁边直接挖一口井来获得水,也可以用管子从任意有水的牧草那里来获得水。
    在第i颗牧草旁边挖一口井的代价为Wi(1 <= W_i <= 100,000),用管子连接第i与第j颗牧草的代价为Pij(1 <= Pij <=100,000; Pij = Pji; Pii=0)
    请求出Farmer John浇灌这些牧草花费的最小代价。

    入力形式

    第一行,一个整数N
    第二行到第N+1行,行i+1表示Wi
    第N+2行到第2N+1行,行N+1+i包含N个用空格分隔开来的整数,每行第j个数字即是Pij

    出力形式

    仅一行,Farmer John浇灌这些牧草的最小代价。

    サンプル入力






    0 2 2 2 
    2 0 3 3 
    2 3 0 4 
    2 3 4 0

    サンプル出力

    9


    ソース  [Usaco Oct08 Gold] Watering Hole