Time-8 - +K Roading

2 secs 1024 MB

matcharate12

問題

提出

テストケース

解説

この問題は 01BFS を問います。

島 $a$ にいる時点での行動は、次のいずれかです。

島 $a+K$ をつなぐ橋を作る(魔法を $1$ 回使う) ...①
島 $a$ とつなぐ島 $p_1,p_2,...,p_n$ のいずれか $1$ つの島に行く(魔法は使わない) ...②

①について、この橋は魔法を使う必要があります。魔法を使うことで島 $a+K$ と隣接している島に移動することが可能となります。
②について、魔法を使わずに移動することが可能です。

こうしてみると、この問題は次の問題に帰着することができます。

有向グラフが与えられ、島と島をつなぐ辺には $0,1$ の重みが付加されている。
このとき島 $A_i,B_i$ を互いにつなぐ辺には重み $0$ 、それ以外の辺※にはすべて重み $1$ が付加されている。
島 $1$ から島 $N$ まで辺の上を移動することでたどり着くとき、歩いた辺の重みの総和の最小値を求めよ。

これは単一始点最短経路探索(ダイクストラ法など)問題に他なりません。しかし今回は $0,1$ のいずれかの重みが加えられているので、これは 01BFS といった探索法を用いることにより解くことができます。

計算量は $O(N+M)$ でこの問題を解くことができました。以下が解答例になります。

※「それ以外の辺」というのはある $1$ 以上 $N-K$ 以下の整数 $a$ であって、すべての辺の情報において $(A_i,B_i)\ne(a,a+K)$ が成り立つとき、島 $a,a+K$ を互いにつなぐ(仮想的な)橋をいいます。この橋を建設するのに魔法を $1$ 回要しますから、重み $1$ を付加してあげる必要があります。

追記: 想定解の修正をしました。島 $a$ から島 $a+K$ に橋を作ることはできますが、島 $a$ から島 $a-K$ には橋をかけることはできないことに注意してください。

C++

xxxxxxxxxx
 
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(A)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge {
    int to;
    ll cost;
    //int from;
};
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<vector<int>>;
using EGraph = vector<Edge>;
using SGraph = vector<set<ll>>;
template <typename T>
int siz(T& a){ return (int)a.size(); }
using namespace std;
​
int main(){
    int n,m,k; cin >> n >> m >> k;
    vector<vector<P>> G(n);
​
    set<P> st;
    rep(i,m){
        int a,b; cin >> a >> b;
        a--; b--;
        G[a].push_back({b,0});
        G[b].push_back({a,0});
        st.insert({a,b});
        st.insert({b,a});
    }
​
    rep(i,n-k){
        if(st.count({i,i+k})) continue;
        G[i].push_back({i+k,1});
    }
​
    vector<ll> dist(n,inf);
    dist[0] = 0;
    deque<int> Q;
    Q.push_back(0);
​
    while(siz(Q)){
        int v = Q.front(); Q.pop_front();
        for(auto& e : G[v]){
            int cost = e.second,to = e.first;
            ll d = dist[v]+cost;
            if(d < dist[to]){
                dist[to] = d;
                if(cost) Q.push_back(to);
                else Q.push_front(to);
            }
        }
    }
    cout << (dist[n-1] < inf ? dist[n-1] : -1);
}
​

Python

xxxxxxxxxx
 
from collections import deque
​
inf = 10**9
n,m,k = map(int,input().split())
G = [[] for i in range(n)]
​
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append([b,0])
    G[b].append([a,0])
​
Q = deque()
for i in range(n-k):
    #if ([i,0] in G[i+k] or [i+k,0] in G[i]): continue
    G[i].append([i+k,1])
​
D = [inf for i in range(n)]
D[0] = 0
Q.append(0)
while len(Q):
    v = Q[-1]
    Q.pop()
    for nv in G[v]:
        to = nv[0]
        cost = nv[1]
        d = D[v]+cost
        if d < D[to]:
            D[to] = d
            if cost: Q.append(to)
            else: Q.appendleft(to)
​
print(D[n-1] if D[n-1] < inf else -1)