글 읽기 - 머그컵 질문이요

didwlvv 7년 전 0

소수마을인데 일단 소수를 구해놓고 큐를 돌립니다. 큐에서 나온값은 현재 위치이고 그것을 비와 비교를 해서 소수로 갈수 있으면 그거리를 비교해서 최소값을 저장해 놓습니다. 포문은 마을 수만큼 돌리고 만약에 마을을 밟았다면 체크를 하는식으로 진행하였습니다. 15퍼에서 틀리는데 어디가 틀린지 잘 모르겠습니다. 헬프점여

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;
struct Data{
    int x,y,hap;
};
int n;
Data a,b;
Data city[4005];
int chk[4005];  bool sosu[10000];
int main(){
    for(int i=2; i<10000; i++){
        if(!sosu[i]){
            for(int j= i*2; j<10000; j+=i){
                sosu[j]=true;
            }
        }
    }
    
    
    scanf("%d %d %d %d", &a.x, &a.y, &b.x, &b.y);
    
    scanf("%d", &n);
    
    for(int i=0; i<n; i++){
        scanf("%d %d", &city[i].x, &city[i].y);
    }
    
    queue<Data>q;
    q.push({a.x,a.y,0});
    
    int res=0x3f3f3f3f;
    while(!q.empty()){
        Data now =q.front();    q.pop();
        
        
        int t =sqrt((now.x-b.x)*(now.x-b.x) + (now.y-b.y)*(now.y-b.y));
        
        if(sosu[t]==false){
            if(now.hap + t < res)
                res=now.hap + t;
            continue;
           
        }
        
        
        for(int i=0; i<n; i++){
            Data next =city[i];
            int d =sqrt((now.x-next.x)*(now.x-next.x) + (now.y-next.y)*(now.y-next.y));
          
            if(sosu[d]==false && chk[i]==0){
                chk[i]=1;
                q.push({next.x,next.y,now.hap + d});
            }
        }
    }
    if(res ==0x3f3f3f3f)
        cout <<"-1"<<endl;
    else
        cout << res <<endl;
    return 0;
}

doju 7년 전 1

1. 0과 1은 소수가 아닙니다.

2. hap에 들어가는 값이 해당 (x, y)로 가는 최단 거리인지 보장되지 않습니다. BFS로 최단거리를 구하는 것은 모든 간선의 길이가 같을 때에만 제대로 작동합니다.

input
5 0 0 5
1
2 2

output
6

didwlvv 7년 전 0

감사합니다. 그래서 제가 소스를 다익스트라로 바꿔보니까 0,1,도 지우고 35 퍼까지 올라가다 또틀리네요.

님이 말한 부분은 고친거 같은데 혹시 잘못했나요? 한번 봐주시면 감사하겠습니다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;
struct Data{
    int x,y,hap,i;
};
int n;
Data a,b;
Data city[4005];
int chk[4005];  bool sosu[10000];   int dist[4005];
int main(){
    sosu[0]=true;
    sosu[1]=true;
    for(int i=2; i<10000; i++){
        if(!sosu[i]){
            for(int j= i*2; j<10000; j+=i){
                sosu[j]=true;
            }
        }
    }
    
    
    scanf("%d %d %d %d", &a.x, &a.y, &b.x, &b.y);
    
    scanf("%d", &n);
    
    for(int i=1; i<=n; i++){
        scanf("%d %d", &city[i].x, &city[i].y);
    }
    memset(dist,0x3f, sizeof dist);
    
    dist[0]=0;
    queue<Data>q;
    q.push({a.x,a.y,0,0});
    
    int res=0x3f3f3f3f;
    while(!q.empty()){
        Data now =q.front();    q.pop();
        
        
        int t =sqrt((now.x-b.x)*(now.x-b.x) + (now.y-b.y)*(now.y-b.y));
        
        if(sosu[t]==false){
            if(now.hap + t < res)
                res=now.hap + t;
           
            
        }
        
        // 이부분 수정함------------------
        for(int i=1; i<=n; i++){
            Data next =city[i];
            int d =sqrt((now.x-next.x)*(now.x-next.x) + (now.y-next.y)*(now.y-next.y));
            
            if(sosu[d]==false){
                if(dist[i] > dist[now.i] + d){
                    dist[i] = dist[now.i] + d;
                    q.push({next.x,next.y,now.hap + d,i});
                }
            }
        }
    }
    if(res ==0x3f3f3f3f)
        cout <<"-1"<<endl;
    else
        cout << res <<endl;
    return 0;
}

doju 7년 전 0

hap이 dist를 따라 갱신되고 있지 않습니다.

input
6 4 2 4
3
0 3
8 6
10 8

output
17

didwlvv 7년 전 0

감사합니다. 좀 더 공부를 해야겠습니다 ㅜㅜ

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

문제

문제

출처

ICPC

머그컵 질문이요

didwlvv 7년 전 0

doju 7년 전 1

didwlvv 7년 전 0

doju 7년 전 0

didwlvv 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말