글 읽기 - [23840]힌트 얻을 수 있을까요?

tjdahr25 2년 전 0

기존 외판원 문제와 같이

[노드번호][bit] 형태로 2차원 배열을 선언하기엔 p의 범위가 20까지고, n의 범위가 100000까지라 너무 크더군요..

각 노드와 그때 bit에 대해 최소 거리를 저장할 수 있는 방법중에서 더 효율적으로 저장할 수 있는 방법이 무엇이 있을까요?

dk10211 2년 전 0

p개의 정점들에 대해 각각 다익스트라를 돌려서 p*p 배열에 값을 넣고 각각 시작 지점과 끝 지점으로 가는 비용만 저장하면 기존 외판원 문제와 비슷해지고 나머지 n개의 정점을 생각할 필요가 없어요

tjdahr25 2년 전 0

그런 아이디어가 있었군요..!

시작, 중간, 끝 지점들을 모두 포인트로 저장해 시작에서 끝까지 모든 정점을 한번씩 탐색하는 경우로 생각해서 문제를 풀었습니다.

근데 자꾸 81퍼센트에서 WA가 뜨네요.. 변수형도 잘 맞춘 것 같은데 뭐가 문제일까요ㅠㅠ..

#include <iostream>
#include <queue>
#include <iostream>
#include <cstring>
#include <algorithm>
#define pii pair<int, int>
using namespace std;

vector <vector<pii>> graph;
vector <int> point;
bool visit[100001];
int bitidx[100001];
long long dist[22][22];
long long distmp[100001];
long long dp[22][1<<22];

int n,m,x,z,p,a,b,c;

void dijkstra(int start){
    memset(visit, false, sizeof(visit));
    memset(distmp, -1, sizeof(distmp));
    priority_queue <pii, vector<pii>, greater<pii>> q;
    q.push({0, start});
    distmp[start] = 0;

    while(!q.empty()){
        pii curr = q.top();
        q.pop();
        if(visit[curr.second]) continue;
        visit[curr.second]=true;
        if(bitidx[curr.second]>-1) dist[bitidx[start]][bitidx[curr.second]] = curr.first;
        for(int i=0;i<graph[curr.second].size();i++){
            int dst = graph[curr.second][i].first;
            int weight = graph[curr.second][i].second;
            if(distmp[dst]==-1 || distmp[dst] > distmp[curr.second]+weight){
                distmp[dst] = distmp[curr.second]+weight;
                q.push({distmp[dst], dst});
            }
        }
    }
}

long long go(int idx, int bit){
    if(idx == z) {
        if(bit==(1<<(p+2))-1) {
            return dp[bitidx[idx]][bit]=0;
        }
        else return -1;
    }

    if(dp[bitidx[idx]][bit]!=0) return dp[bitidx[idx]][bit];

    long long ret = -1;
    for(int i=0;i<point.size();i++){
        int dst = point[i];
        if(dist[bitidx[idx]][bitidx[dst]]==-1) continue;
        
        int next_bit = (bit | (1<<bitidx[dst]));

        if(next_bit==bit) continue;

        long long tmp = go(dst, next_bit);
        if(tmp<0) continue;

        if(ret==-1 || ret > tmp+dist[bitidx[idx]][bitidx[dst]]) {
            ret = tmp+dist[bitidx[idx]][bitidx[dst]];
        }
        
    }
    return dp[bitidx[idx]][bit]=ret;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m;
    graph.resize(n+1);
    memset(dist, -1, sizeof(dist));
    memset(bitidx, -1, sizeof(bitidx));
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }
    cin>>x>>z>>p;
    bitidx[x]=0, bitidx[z]=p+1;
    point.push_back(x);
    for(int i=1;i<=p;i++){
        cin>>a;
        bitidx[a]=i;
        point.push_back(a);
    }
    point.push_back(z);
    for(int i=0;i<point.size();i++){
        dijkstra(point[i]);
    }
    cout<<go(x,1);
    return 0;
}
    

dk10211 2년 전 0

제출해보니까 자료형 문제네요.

다익스트라를 돌릴때 int 범위를 벗어나서 그래요. 우선순위 큐 선언을 pii대신 pair<long long,int>넣으시고 int weight 대신 long long weight으로 하면 AC받아요

tjdahr25 2년 전 0

아 그렇군요!!!!!

바보같은 실수를 하고 있었네요..

또 하나 배워갑니다

정말 감사합니다!!

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

문제

문제

출처

ICPC

[23840]힌트 얻을 수 있을까요?

tjdahr25 2년 전 0

dk10211 2년 전 0

tjdahr25 2년 전 0

dk10211 2년 전 0

tjdahr25 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말