글 읽기 - 18232 정말 모르겠습니다.

dlftls38 4년 전 1

처음엔 탑다운 DP로 풀어봤는데 자꾸 틀려서

BFS로 해봤는데도 안됩니다.

테스트 케이스가 잘못된거라고 믿고싶지만 맞은 사람들이 있어서 아닌 것 같고

정말 왜 틀리는지 모르겠습니다,

#include <bits/stdc++.h>
#define INF 987654321
#define MOD 1000000009
#define pi 3.141592
using namespace std;
typedef pair<int,int> pii;
int teleport[313131];
int cost[313131];
int n,m;
int s,e;
int main(){
    cin>>n>>m;
    cin>>s>>e;
    int i,j;
    for(i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        teleport[x]=y;
        teleport[y]=x;
    }
    for(i=0;i<=310000;i++){
        cost[i]=INF;
    }
    queue<pair<int,int>> q;
    q.push({s,0});
    while(1){
        int cur = q.front().first;
        int cnt = q.front().second;
        q.pop();
        if(cur<1 || cur>n || cost[cur]<=cnt)continue;
        cost[cur]=cnt;
        if(cur==e){
            printf("%d",cnt);
            return 0;
        }
        q.push({cur+1,cnt+1});
        q.push({cur-1,cnt+1});
        if(teleport[cur]>0)
            q.push({teleport[cur],cnt+1});
    }
}

snrnsidy 4년 전 2

반례드립니다

100 3
1 33
1 33
1 30
30 33

답:1 출력:2

dlftls38 4년 전 0

텔레포트가 하나만 있다는게 한 곳으로만 갈 수 있다는 뜻 아니었나보네요

근데 이전에 풀었던 DP는 그 부분을 보완할 수 있는데 DP는 풀 수 없는 방법인건가요??

#include <bits/stdc++.h>
#define INF 987654321
#define MOD 1000000009
#define pi 3.141592
using namespace std;
typedef pair<int,int> pii;
vector<int> link[313131];
int n,m;
int s,e;
int dp[313131];
int solve(int cur){
    int &ret = dp[cur];
    if(cur == e){
        return 0;
    }
    if(ret != -1){
        return ret;
    }
    ret = INF;
    int size = link[cur].size();
    for(int i=0;i<size;i++){
        ret = min(ret, solve(link[cur][i])+1);
    }
    if(cur+1<=n)
        ret = min(ret, solve(cur+1)+1);
    if(cur-1>=1)
        ret = min(ret, solve(cur-1)+1);
    return ret;
}
int main(){
    cin>>n>>m;
    cin>>s>>e;
    int i,j;
    for(i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        link[x].push_back(y);
        link[y].push_back(x);
    }
    memset(dp,-1,sizeof(dp));
    cout<<solve(s);
}

djm03178 4년 전 3

dp는 그래프의 형태가 DAG가 아니면 일반적으로는 쓸 수 없습니다. 사이클에 대한 대처를 하지 못하기 때문입니다.

dlftls38 4년 전 0

그렇군요 감사합니다.

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

문제

문제

출처

ICPC

18232 정말 모르겠습니다.

dlftls38 4년 전 1

snrnsidy 4년 전 2

dlftls38 4년 전 0

djm03178 4년 전 3

dlftls38 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말