[PGBATTLE2020_ましゅまろ4]辞書順最小最短経路 (Minimum Lexicographical Shortest Path)

2021年10月14日 22:02

[Q] https://products.sint.co.jp/q_list_2020
[解答例] https://products.sint.co.jp/hubfs/resource/topsic/pgb2020/code.pdf

1. Nからダイクストラして、N->1までの距離を出しておく。
2. 1->Nに向けて、距離が1ずつ縮まる部屋かつ、部屋番号が小さいものを採択すればよさそう。

Q. 
4 5

1 2
1 3
2 3
2 4
3 4

1. グラフを張る。
コストを知るための逆辺グラフと、経路を知るための順路グラフを用意。
・順路 G
G[1] = {2, 3}
G[2] = {3, 4}
G[3] = {4}
G[4] = {}

・ダイクストラ R
R[1] = {}
R[2] = {1}
R[3] = {1, 2}
R[4] = {2, 3}

2. N を始点としたダイクストラで、各部屋への距離を求める。
D[1] = 2
D[2] = 1
D[3] = 1
D[4] = 0

3. 1 を出発地点として、Nまで歩数 2 でいけるルートを走査する。
・1 の処理。
歩数2 -> 1なので、歩数1の部屋を選ぶ。

G[1] = {2, 3}
D[2] = 1 // OK
D[3] = 1 // OK

辞書順で値の小さい 2 へ移動する。

・2の処理
歩数1 -> 0 なので、歩数0の部屋を選ぶ。

G[2] = {3, 4}
D[3] = 1 > 0 // NG
D[4] = 0 // OK

4に進む。

A. 1 2 4

実装

int main(){
 cin.tie(0);
 ios::sync_with_stdio(0);
 cout << fixed << setprecision(10);
 
 ll N, M;
 cin >> N >> M;
 
 graph g(N+1); // 0index ~ 
 vector<ll> G[N+1]; // 1->Nの道
 rep(i, M){
   ll A, B;
   cin >> A >> B;
   --A, --B;
   g.add_edge(B, A, 1); // N->1のコスト
   G[A].push_back(B);
 }
 g.dijkstra(N-1);
 if (g.d[0] == oo){
   cout << -1 << endl;
   return 0;
 }
 
 // 1から探索。
 ll now = 0;
 queue<ll> ans;
 ans.push(0);
 
 for(ll dis = g.d[0]-1; dis>=0; --dis){
   priority_queue<ll, vector<ll>, greater<ll>> Q;
   for(auto v: G[now]){
     if (g.d[v] > dis) continue;
     Q.push(v);
   }
   ans.push(Q.top());
   now = Q.top();
 }
 while (!ans.empty()){
   cout << ans.front()+1; ans.pop();
   if (!ans.empty()) cout << " ";
   else cout << endl;
 }
}

https://atcoder.jp/contests/arc128/submissions/26688097

--- 10/13 嘘解放 ---
経路を復元できればいいかな、と思う。
1. 0からスタートしてbfs。
2. N-1に到達した時点で経路復元。
3. 同じ手数でゴールするものが複数ありそうなので、set<vector>に保存しておく。

Q. priority_queue？
A. 1->3 と 2->3
があったときに、3に合流した時点で1->3だけを採用したい。
ので、部屋番号が小さい部屋から探索すればよさそうなので、priority_queueでqueueの処理を実施。

※嘘解かもしれない
1->8->2->3->goal
1->4->5->3->goal
があったときに、3に合流した時点でprevs[3]=2を優先してしまうので、
1->8->2->3->9を採用してしまう。。

goalから1にむけて探索し、最後はindexが小さい部屋を採用すればよさそう

実装

vector<ll> G[100010];
ll prevs[100010]; // p[now] = prev
ll N, M;
set<vector<ll>> cand; // ゴールへの経路をためる

// ゴールまでの道がわかったら、経路復元
void init_cand(){
 vector<ll> ret;
 ll now=N-1;
 while (now>0){
   ret.push_back(now+1);
   now = prevs[now];
 }
 ret.push_back(1);
 reverse(all(ret));
 cand.insert(ret);
}

bool bfs(priority_queue<ll, vector<ll>, greater<ll>> &Q){
 bool fin=false;
 while (!Q.empty() && fin==false){
   ll sz = Q.size();
   queue<ll> nxQ;
   rep(i, sz){
     ll q = Q.top(); Q.pop();
     for(auto u: G[q]){
       // 1->3 と 2->3があったら、1->3だけ採用
       // 1から先に探索すればいい。priority_queue。
       if (prevs[u] > -1) continue; // もう見た
       prevs[u] = q;
       if (u == N-1){
         init_cand();
         fin = true;
         prevs[u] = -1;
       }
       // 次の行先をためておく
       nxQ.push(u);
     }
   }
   // 次の行先をpriority_queueにいれる
   while (!nxQ.empty()){
     Q.push(nxQ.front()); nxQ.pop();
   }
 }
 return fin;
}

int main(){
 cincout();
 
 cin >> N >> M;
 rep(i, M){
   ll a, b;
   cin >> a >> b;
   --a, --b;
   G[a].push_back(b);
 }
 // 経路復元。-1:まだここ通ってない
 rep(i, N) prevs[i] = -1;
 prevs[0]=0;
 
 priority_queue<ll, vector<ll>, greater<ll>> Q;
 Q.push(0);
 bool is_fin=bfs(Q);
 if(is_fin == false){
   cout << -1 << endl;
   return 0;
 }
 vector<ll> ans=*(cand.begin());
 ll asz=ans.size();
 rep(i, asz){
   cout << ans[i];
   if (i<asz-1) cout << " ";
   else cout << endl;
 }
}

[PGBATTLE2020_ましゅまろ4]辞書順最小最短経路​ (Minimum Lexicographical Shortest Path)

いいなと思ったら応援しよう！

[PGBATTLE2020_ましゅまろ4]辞書順最小最短経路 (Minimum Lexicographical Shortest Path)