Submission #69187091

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, m;
  cin >> n >> m;

  vector<long long> w(n);
  for (int i=0; i<n; i++) {
    cin >> w.at(i);
  }

  // 隣接リストに受け取る
  vector<int> u(m), v(m);
  vector<set<int>> graph(n);
  for (int i=0; i<m; i++) {
    cin >> u.at(i) >> v.at(i);
    u.at(i)--;
    v.at(i)--;
    graph.at(u.at(i)).emplace(v.at(i));
    graph.at(v.at(i)).emplace(u.at(i));
  }

  //////////////// 出力変数定義 ////////////////

  vector<long long> result;

  //////////////////// 処理 ////////////////////

  // DPテーブル
  // dp.at(i).at(j) は、n回中i回移動して頂点jに到達したときの消費燃料
  // ただし、nターンになるまで何も食べずに移動し続けるコスト分も加算している
  vector<vector<long long>> dp(n+1,vector<long long>(n,1e18));

  // テーブル更新
  for (int i=0; i<n; i++) {

    // スタートするターンを遅らせる場合を考慮する
    dp.at(i).at(0) = 0;

    // 頂点ごとに離接頂点に情報を配っていく
    for (int j=0; j<n; j++) {

      // まず食事をする
      dp.at(i).at(j) += w.at(j)*(n-i);

      // 配る
      for (int next : graph.at(j)) {
        dp.at(i+1).at(next) = min(dp.at(i+1).at(next),dp.at(i).at(j));
      }

    }

  }

  // スタート地点はコスト0でいい
  dp.at(n).at(0) = 0;

  // n回移動を終えた後のデータが答え
  result = dp.at(n);

  //////////////////// 出力 ////////////////////

  for (int i=0; i<n; i++) {
    cout << result.at(i) << endl;
  }

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result