mini notes

競技プログラミングの解法メモを残していきます。

第二回全国統一プログラミング王決定戦予選 D - Shortest Path on a Line(600)

D - Shortest Path on a Line

概要

1からNまでの番号が付いた頂点がある。最初は辺がない。
M個のパラメータLi, Ri, Ciが与えられる。パラメータLi, Ri, Ciに対し、下記を行う。

  • Li ≦ s < t ≦ Ri なる全ての頂点(s, t)に対し、長さCiの辺を追加する

上記の作業をすべて終えた後、頂点1から頂点Nまでの最短距離を求めよ。
（頂点1から頂点Nまでたどり着けない場合は-1を出力せよ）

制約

2 ≦ N ≦ 10^5
1 ≦ M ≦ 10^5
1 ≦ Ci ≦ 10^9

方針①

d[i] :頂点1から頂点iまでの最短距離　とすると、dは広義単調増加である。
そのため、1 ≦ i ≦ N - 1なるiについて、(i+1, i)を結ぶ長さ0の辺を追加しても、最短距離に影響しない。
また、M個の各パラメータ(Li, Ri, Ci)について、このパラメータを(Li, Ri)を結ぶ長さCiの辺として考える。
このとき、上記をあわせたN - 1 + M本の辺でもって頂点1から頂点Nまでの最短距離が実現される。
最短距離はDijkstra法で計算すればよい。

方針②

パラメータ(Li, Ri, Ci)によって追加される辺について、終点がRiのものだけを考えればよい。
このとき、dp[i]:頂点1から頂点iまでの最短距離　とすると、dpは下記のように遷移する。
dp[x] = min_{i | x = Ri}(min_{Li ≦ s < Ri}(dp[s] + Ci ))

Riの小さい順にdpが確定してゆくことになるので、Riが小さい順に上記dpを遷移させてゆく。
dpの区間最小を取得する必要があるため、dpはSegmentTreeで実装する。

解答①

Submission #9322163 - NIKKEI Programming Contest 2019-2

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
// dijkstra 蟻本
struct edge {ll to, cost;};
typedef pair<ll, ll> P; // firstはsからの最短距離, secondは頂点の番号
const ll INF = LLONG_MAX / 2;
const int max_n = 101010;
 
int n;
vector<edge> g[max_n];
ll d[max_n];
 
void dijkstra(ll s){
	fill(d, d + n, INF);
	d[s] = 0;
 
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,s));
 
	while(!que.empty()){
		P p = que.top();
		que.pop();
 
		ll v = p.second;
		if(d[v] < p.first) continue; //後から最短パスが見つかった場合、先にqueに入っているものはここではじかれる
 
		for(ll i = 0; i < g[v].size(); i++){
			edge e= g[v][i];
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int m;
	cin >> n >> m;
 
	rep(i, m){
		int l, r;
		ll c;
		cin >> l >> r >> c;
		l--; r--;
		g[l].push_back((edge){r, c});
	}
 
  rep(i, n){
    g[i+1].push_back((edge){i, 0});
  }
  
  dijkstra(0);
  ll dist = d[n-1];
 
  if(dist == INF){
    cout << -1 << endl;
  }else{
    cout << dist << endl;
  }
	
}

解答②

Submission #9322063 - NIKKEI Programming Contest 2019-2

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
struct edge{
	int l, r;
	ll c;
};
 
template< typename Monoid >
struct SegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;
 
  int sz;
  vector< Monoid > seg;
 
  const F f;
  const Monoid M1;
 
  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }
 
  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }
 
  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
 
  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
 
  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }
 
  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }
};
 
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n, m;
	cin >> n >> m;
 
	vector<edge> edges;
	rep(i, m){
		int l, r;
		ll c;
		cin >> l >> r >> c;
		l--; r--;
		edges.push_back((edge){l, r, c});
	}
 
	sort(edges.begin(), edges.end(), [](edge e1, edge e2){
		return e1.r < e2.r;
	});
 
	ll INF = LLONG_MAX / 2;
	SegmentTree<ll> seg(n, [](ll a, ll b) { return min(a, b); }, INF);
	seg.update(0, 0);
	for(edge e : edges){
		ll mn = seg.query(e.l, e.r);
		ll val = seg.query(e.r, e.r+1);
		seg.update(e.r, min({val, mn + e.c, INF}));
	}
 
	ll ans = seg.query(n - 1, n);
	if(ans == INF){
		cout << -1 << endl;
	}else{
		cout << ans << endl;
	}
 
}