第七回 アルゴリズム実技検定 K問題

PAST007K

まず min cost, 次に max scenery. また，コストは全て正． 答えは，min cost となるパス \(1 \rightarrow N\) 全体から max scenery をとる．
これは Dijikstra を (cost, -scenery ) で昇順ソートの priority_queue で行えば良い．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

int main() {

  ll n,m;

  cin >> n >> m;

  vll a(n); rep(i,n) { cin >> a[i]; }

  rep(i,n) a[i] *= -1;

  using ED = pair<int, ll>; // vx, cost

  vector<vector<ED>> ed(n);

  rep(i,m){

    ll t,x,y; cin >> x >> y >> t;

    --x,--y;

    ed[x].emplace_back(y, t);

    ed[y].emplace_back(x, t);

  }

  using P = pair<ll, int>; // dis, vx

  using Q = pair<ll, ll>; // cost, scenery

  min_priority_queue<P> q; // dis, vx

  vector<Q> dis(n);

  auto push = [&](ll v, ll co, ll sc) -> void {

    if(chmin(dis[v], {co, sc})) q.push({co, v});

  };

  rep(i,n){

    dis[i] = {INFL, 0};

  }

 

  push(0, 0, a[0]);

  while(q.size()){

    auto [_, cu] = q.top();

    q.pop();

    for(ED e: ed[cu]){

      auto [ne, t] = e;

      push(ne, dis[cu].first + t, dis[cu].second + a[ne]);

    }

  }

  assert(dis[n-1].first < INFL);

  cout << -dis[n-1].second << endl;

  return 0;

}