14207 - 약수 도로

step 1

모든 도시를 정점으로, 도시 간 이동을 간선으로 표현하면 쉽게 문제를 풀수 있습니다. 물론 시간과 공간만 충분하다면 말이죠. 조금 더 표율적으로 하기 위해 정점 $X$ 를 $X$의 배수인 모든 정점을 하나로 뭉쳐 놓은 것이라 생각할 수 있습니다.

step 2

답이 0이나 1인 경우는 너무 쉬우니 생략하겠습니다. 아래 예시는 예제 입력 4를 기준으로 하고 있습니다.

정점들을 모두 표시한 다음 시작 점을 포함하는 출발 정점들을 표시해 봅시다.

 

마찬가지로 도착 정점도 표시해 줍니다.

 

도착 정점 $X$와 출발 정점 $Y$가 있을 때 $LCM(x,y) \le N$ 이면 $X$에서 $Y$로 가중치 0인 간선을 만들어 줍니다. 아래는 간선의 일부만 만들었습니다.

 

이제 BFS를 돌리면 답을 알 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
long long int b1[2000],b2[2000],c[2000];
queue<long long int> q;
queue<long long int> q1;
long long int gcd(long long int x, long long int y) { return y == 0 ? x : gcd(y, x % y); }
int main() {
    long long int n, x, y, i,m;
    scanf("%lld%lld%lld%lld", &n, &x, &y, &m);
    if (x == y) { printf("0"); return 0; }
    for (i = 1;i <= m;i++) {
        scanf("%lld", &b1[i]);
    }
    for (i = 1;i <= m;i++) {
        scanf("%lld", &b2[i]);
        if (x % b1[i] == 0) {
            q.push(b2[i]);
            q1.push(1);
            c[i] = 1;
            if(y%b2[i]==0) { printf("1"); return 0; }
        }
    }
    while (q.size()) {
        long long int num = q.front(), cnt=q1.front();
        q.pop(); q1.pop();
        for (i = 1;i <= m;i++) {
            if (c[i] == 1) continue;
            if (num * b1[i] / gcd(num, b1[i]) <= n) {
                if (y % b2[i] == 0) { printf("%lld",cnt+1); return 0; }
                q.push(b2[i]);
                q1.push(cnt + 1);
                c[i] = 1;
            }
        }
    }
    printf("-1");
    return 0;
}