문제를 잘못읽어 뻘짓을 좀 했다.
중간에 "어떤 방법이든 최소 두 번 엘리베이터를 타야한다. "라는 문장만 보고 모든 경우에서 해당되는지 알았는데
예시를 든 경우에 대해 말하는 거였다.
처음에는 이 문제를 엘리베이터가 갈 수 있는 층이 등차수열($ax + k$ 형태)로 되있기 때문에
두 엘리베이터가 서로 갈 수 있는지 여부를 부정방정식($ax+by=c$ 형태)을 풀어서 해결하려 했으나
너무 복잡해져서 포기했다.
※( Extended Uclidean 알고리즘을 쓴 후 특수 해를 뽑은다음에 일반해를 구한다.
그 후에 두 일반해를 넣었을 때 [0, N]의 범위 안에 들어오는지 확인을 해야 될듯 싶다. )
해당 엘리베이터에서 범위 내에 갈 수 있는 모든 층수를 엘리베이터와 연결하여 그래프를 만들었다.
그 후 Dijkstra 비슷하게 돌리면 답이나온다.
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define INF 987654321
#define MAX 100000+101
int N, M, S, E;
int dist[MAX];
int par[MAX];
vector<int> adj[MAX];
void bfs() {
queue<int> q;
fill(par, par + MAX, -1);
fill(dist, dist + MAX, INF);
q.push(E);
dist[E] = 0;
while (!q.empty()) {
int here = q.front();
q.pop();
for (auto next : adj[here]) {
if (dist[next] == INF) {
dist[next] = dist[here] + 1;
par[next] = here;
q.push(next);
}
}
}
}
int main() {
scanf("%d%d", &N, &M);
for (int m = 1;m <= M;m++) {
int a, b;
scanf("%d%d", &b, &a);
// ax + b
for (int n = b;n <= N;n += a) {
adj[n].push_back(m + 100000);
adj[m + 100000].push_back(n);
}
}
scanf("%d%d", &S, &E);
bfs();
if (dist[S] == INF)
printf("-1\n");
else {
printf("%d\n", dist[S] / 2);
for (int i = par[S];i>=0;i = par[par[i]])
printf("%d\n", i - 100000);
}
return 0;
}
| cs |
댓글 없음:
댓글 쓰기