글 읽기 - 5%에서 시간 초과를 돌파할 실마리가 없을까요

seokgukim 1년 전 0

일단 다음과 같은 논리로 진행했습니다.

입력받은 각 역 이름에 대해 해싱해 가며 각 역 사이의 간선을 vector로 관리한다.
입력받은 쿼리에 대해 시작역/도착역 이름을 해싱한 값을 이용해 너비 우선 탐색을 돌린다.
너비 우선 탐색의 특성상, 가장 먼저 도착역에 도달했을 때의 깊이에서 최소 시간이 될 것이므로, 도착역에 도달하면 바로 값을 리턴하고 출력한다.

가능한 모든 경우를 상정해야 하므로 모든 가능한 간선에 대해 탐색했는데, 계속 5%에서 시간 초과가 나네요.

일단 해싱 방법은 여러가지를 시도해 봤지만 전혀 나아지는게 없는 듯 하고...

이 외의 접근 방식은 잘 떠오르지 않아서 혹여나 실마리나마 제공해주실 수 있을까 여쭤봅니다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <memory.h>
#define MOD 1e15 + 19
using namespace std;
typedef long long ll;

int N, M, cc, cnt;
string s, p;
ll base = 31, mod = MOD;
unordered_map<ll, int> mm;
vector<int> path[200001];
bool visit[200001];

ll rabin_hash(string s) {
    ll ans = 0;
    for (char ch : s) {
        ans = (ans * base + ch) % mod;
    }
    return ans;
}

int minpath(int start, int end) {
    if (start == end) return 0;
    queue<pair<int, int>> q;
    q.push({ 0, start });
    visit[start] = 1;
    while (!q.empty()) {
        int depth = q.front().first + 1;
        int cur = q.front().second;
        q.pop();

        for (int j = 0; j < path[cur].size(); j++) {
            int next = path[cur][j];
            if (visit[next]) continue;
            visit[next] = 1;
            if (next == end) return depth << 1;
            q.push({ depth, next });
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M;
    while (N--) {
        cin >> cc;
        int prev = 0;
        while (cc--) {
            cin >> s;
            ll hs = rabin_hash(s);
            if (mm.find(hs) == mm.end()) mm[hs] = ++cnt;
            int cur = mm[hs];
            if (prev) path[prev].push_back(cur), path[cur].push_back(prev);
            prev = cur;
        }
    }
    while (M--) {
        cin >> s >> p;
        memset(visit, 0, sizeof(visit));
        int mp = minpath(mm[rabin_hash(s)], mm[rabin_hash(p)]);
        cout << mp << "\n";
    }
}

bnb2011 1년 전 2

현재 풀이대로라면, 매 쿼리마다 BFS를 이용해 최단 거리를 찾게 되므로 시간복잡도가 O(Q(N+M))이 됩니다. 간선이 최대 20만개이므로 TLE가 날 수 밖에 없겠네요.

문제에서 주어지는 환승역의 개수가 최대 20개라는 점을 이용해보시면 풀이에 도움이 되실 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

5%에서 시간 초과를 돌파할 실마리가 없을까요

seokgukim 1년 전 0

bnb2011 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말