SRM 699 div2 hard FromToDivisibleDiv2

問題

問題概要

a[i]の倍数の頂点番号からb[i]の頂点番号へ有向グラフを張ることができる。SからTに行く最小コストを求める問題。

解法

愚直に、(a[i]の倍数) ->　(b[i]の倍数)　の有向グラフをすべてはり、bfsで、到達した点までの距離を更新しながら、最短距離を更新した。これだと、N=100000　a={1},b={1}の場合などで、有向グラフを形成しているところでTLEしてしまう。
そこで、先に、グラフを作らずに、bfsを行っていく最中で、行ける頂点に対して遷移を行う形で書くと、早くなるみたいだけど、ここでも微妙にWAを連発。(1ケース2ケース通らない)。ACコードでやっていることは簡単で、現在の頂点を割り切ることができる、a[i]をさがして、つぎに、それに対応するb[i]の倍数へ遷移させているだけ。ただ、これだけだと、まだTLEのケースが残る。そこで、b[i]の倍数に遷移させたところで、b[i]の倍数に遷移させたことを記録するusedをつくり、一度遷移させていたら、つぎから、遷移させないようにした。 これをdisの値でいじっていたけど、うまくいかなかった。

ミス

これの制約強化.verがdiv1medium　に出ているぽい。解説よんだけど、lcmでやれるみたいな、、

コード

AC

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int dis[100010];
bool used[100010];

class FromToDivisibleDiv2 {
public:
    int shortest(int N, int S, int T, vector <int> a, vector <int> b){

        rep(i, 100010) dis[i] = -1;
        rep(i, 100010) used[i] = false;
        queue<int> q; q.push(S);
        dis[S] = 0;
        while(!q.empty()){
            int u = q.front(); q.pop();
            if(u == T){//ゴール
                return dis[T];
            }

            for (int i = 0; i < a.size(); ++i){
                if(u % a[i] != 0) continue;//a[i]の倍数から作れる辺ではない
                if(used[b[i]])continue; //b[i]を訪れていたら、b[i]の倍数もすでに訪れている
                used[b[i]] = true;//b[i]の倍数を訪れたことを記録
                //(a[i]の倍数) -> (b[i]の倍数) u -> v
                for (int v = b[i]; v <= N; v += b[i]){
                    if(dis[v] != -1) continue;//すでに訪れている
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
            }
        }
        return dis[T];
    }
};

愚直解答 TLE

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

vector<int> G[100010];
int dis[100010];

class FromToDivisibleDiv2 {
public:
    int shortest(int N, int S, int T, vector <int> a, vector <int> b){
        for (int i = 0; i < a.size(); ++i){//i番目
            for (int j = a[i]; j <= N; j += a[i]){//a[i]の倍数
                for (int k = b[i]; k <= N; k += b[i]){//b[i]の倍数
                    G[j].push_back(k);//a[i]の倍数 -> b[i]の倍数
                }
            }
        }

        rep(i, 100010) dis[i] = -1;

        queue<int> q; q.push(S);
        dis[S] = 0;
        while(!q.empty()){
            int u = q.front(); q.pop();
            if(u == T){
                return dis[T];
            }
            for(auto v : G[u]){
                //u -> v
                if(dis[v] != -1) continue;
                q.push(v);
                dis[v] = dis[u] + 1;
            }
        }
        return -1;
    }
};