글 읽기 - 1810번 데이터 확인해주세요~

h0ngjun7 8년 전 4

데이터에 문제가 있어 보입니다...

h0ngjun7 8년 전 1

@baekjoon

ntopia 7년 전 0

데이터에 오류 없는 것 같아요...

h0ngjun7 7년 전 0

@ntopia

실례지만 제 코드에서 의심가는 부분이나 틀린 것으로 보이는 부분을 찾아주실 수 있을까요?...

#include <cstdio>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const double eps = 1e-6;
#define MN 50005
struct Point {
	int x, y;
	bool operator < (const Point p) const {
		if (p.x != x) return p.x < x;
		return p.y < y;
	}
} b[MN], t;
int n, F;
double d[MN];		//d[x] : x번 정점까지의 최단 거리
map <Point, int> c;	//c[p] : 좌표가 p인 점의 정점 번호
vector <int> v[MN];	//v[x] : x번 정점에서 갈 수 있는 징검 다리 번호
struct _Q {
	int who;
	double dist;
	bool operator < (const _Q q) const { return q.dist < dist; }
} now, nxt;
int main() {
	scanf("%d%d", &n, &F);
	n++;
	vector <int> fin; //y = F인 정점의 번호 집합
	
	//1번 징검다리는 (0, 0)
	t.x = t.y = 0;
	c[t] = 1;
	if (F == 0) fin.push_back(1);
	b[1].x = b[1].y = 0; d[1] = 0;

	for (int i = 2; i <= n; i++) {
		scanf("%d%d", &b[i].x, &b[i].y);
		d[i] = -1;
		if (b[i].y == F) fin.push_back(i);
		c[b[i]] = i;
	}

	for (int i = 1; i <= n; i++) {
		for (int px = -2; px <= 2; px++) {
			for (int py = -2; py <= 2; py++) {
				if (px == 0 && py == 0) continue;
				t.x = b[i].x + px;
				t.y = b[i].y + py;
				if (c[t]) v[i].push_back(c[t]);
			}
		}
	}
	
	priority_queue <_Q> Q;
	now.who = 1; now.dist = 0;
	Q.push(now);
	while (!Q.empty()) {
		now = Q.top(); Q.pop();
		if (now.dist > d[now.who] + eps) continue;
		int x = now.who;
		double y = d[x];
		for (auto &z : v[x]) {
			double dx = b[x].x - b[z].x;
			double dy = b[x].y - b[z].y;
			double cost = y + sqrt(dx*dx + dy*dy);
			if (d[z] < 0 || cost < d[z]) {
				nxt.dist = d[z] = cost;
				nxt.who = z;
				Q.push(nxt);
			}
		}
	}
	
	double res = -1;
	for (auto &x : fin) if (res < -eps || res > d[x]) res = d[x];
	
	if (res < -eps) puts("-1");
	else printf("%.lf", res);
}

ntopia 7년 전 0

정수를 출력하는건데 소수 첫째자리까지 출력하고 있어요

h0ngjun7 7년 전 0

%.lf라서 정수로 반올림해서 출력해용. 1f로 잘못 보신 것 같네요. 저거를 곱하기 10한 다음에 롱롱으로 옮겨서 반올림 계산도 직접해봤는데 둘다 60퍼 쯤에서 틀립니다.

h0ngjun7 7년 전 0

답을 곱하기 10한 다음에 롱롱으로 옮겨서 반올림 계산도 직접한 코드입니당.

#include <cstdio>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const double eps = 1e-9;
#define MN 50005
struct Point {
    int x, y;
    bool operator < (const Point p) const {
        if (p.x != x) return p.x < x;
        return p.y < y;
    }
} b[MN], t;
int n, F;
double d[MN];       //d[x] : x번 정점까지의 최단 거리
map <Point, int> c;   //c[p] : 좌표가 p인 점의 정점 번호
vector <int> v[MN];   //v[x] : x번 정점에서 갈 수 있는 징검 다리 번호
struct _Q {
    int who;
    double dist;
    bool operator < (const _Q q) const { return q.dist < dist; }
} now, nxt;
int main() {
    scanf("%d%d", &n, &F);
    n++;
    vector <int> fin; //y = F인 정점의 번호 집합
     
    //1번 징검다리는 (0, 0)
    t.x = t.y = 0;
    c[t] = 1;
    if (F == 0) fin.push_back(1);
    b[1].x = b[1].y = 0; d[1] = 0;
 
    for (int i = 2; i <= n; i++) {
        scanf("%d%d", &b[i].x, &b[i].y);
        d[i] = -1;
        if (b[i].y == F) fin.push_back(i);
        c[b[i]] = i;
    }
 
    for (int i = 1; i <= n; i++) {
        for (int px = -2; px <= 2; px++) {
            for (int py = -2; py <= 2; py++) {
                if (px == 0 && py == 0) continue;
                t.x = b[i].x + px;
                t.y = b[i].y + py;
                if (c[t]) v[i].push_back(c[t]);
            }
        }
    }
     
    priority_queue <_Q> Q;
    now.who = 1; now.dist = 0;
    Q.push(now);
    while (!Q.empty()) {
        now = Q.top(); Q.pop();
        if (now.dist > d[now.who] + eps) continue;
        int x = now.who;
        double y = d[x];
        for (auto &z : v[x]) {
            double dx = b[x].x - b[z].x;
            double dy = b[x].y - b[z].y;
            double cost = y + sqrt(dx*dx + dy*dy);
            if (d[z] < 0 || cost < d[z]) {
                nxt.dist = d[z] = cost;
                nxt.who = z;
                Q.push(nxt);
            }
        }
    }
     
    double res = -1;
    for (auto &x : fin) if (res < -eps || res > d[x]) res = d[x];
     
    if (res < -eps) puts("-1");
    else {
        long long ans = (res + eps) * 10;
        int mod = ans % 10;
        ans /= 10;
        if (mod >= 5) ans++;
        printf("%lld", ans);
    }
}

etaehyun4 7년 전 0

1 0

3 0

하면

-1이 나오네요 ㅎㅎ

입력을 2부터 n+1 까지 받아야 하는거 아닌가요

yukariko 7년 전 0

고쳐드렸습니다

#include <cstdio>
#include <map>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const double eps = 1e-2;
#define MN 50005
struct Point {
    int x, y;
    bool operator < (const Point p) const {
        if (p.x != x) return p.x < x;
        return p.y < y;
    }
} b[MN], t;
int n, F;
double d[MN];       //d[x] : x번 정점까지의 최단 거리
map <Point, int> c;   //c[p] : 좌표가 p인 점의 정점 번호
vector <int> v[MN];   //v[x] : x번 정점에서 갈 수 있는 징검 다리 번호
struct _Q {
    int who;
    double dist;
    bool operator < (const _Q q) const { return q.dist < dist; }
} now, nxt;
int main() {
    scanf("%d%d", &n, &F);
    n++;
    vector <int> fin; //y = F인 정점의 번호 집합
      
    //1번 징검다리는 (0, 0)
    t.x = t.y = 0;
    c[t] = 1;
    if (F == 0) fin.push_back(1);
    b[1].x = b[1].y = 0; d[1] = 0;
  
    for (int i = 2; i <= n; i++) {
        scanf("%d%d", &b[i].x, &b[i].y);
        d[i] = -1;
        if (b[i].y == F) fin.push_back(i);
        c[b[i]] = i;
    }
  
    for (int i = 1; i <= n; i++) {
        for (int px = -2; px <= 2; px++) {
            for (int py = -2; py <= 2; py++) {
                if (px == 0 && py == 0) continue;
                t.x = b[i].x + px;
                t.y = b[i].y + py;
                if (c[t]) v[i].push_back(c[t]);
            }
        }
    }
      
    priority_queue <_Q> Q;
    now.who = 1; now.dist = 0;
    Q.push(now);
    while (!Q.empty()) {
        now = Q.top(); Q.pop();
        if (now.dist > d[now.who] + eps) continue;
        int x = now.who;
        double y = d[x];
        for (auto &z : v[x]) {
            double dx = b[x].x - b[z].x;
            double dy = b[x].y - b[z].y;
            double cost = y + sqrt(dx*dx + dy*dy);
            if (d[z] < 0 || cost < d[z]) {
                nxt.dist = d[z] = cost;
                nxt.who = z;
                Q.push(nxt);
            }
        }
    }
      
    double res = -1;
    for (auto &x : fin) if (d[x] > 0  && (res < -eps || res > d[x])) res = d[x];
      
    if (res < -eps) puts("-1");
    else {
        long long ans = (res + eps) * 10;
        int mod = ans % 10;
        ans /= 10;
        if (mod >= 5) ans++;
        printf("%lld", ans);
    }
}

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

문제

문제

출처

ICPC

1810번 데이터 확인해주세요~

h0ngjun7 8년 전 4

h0ngjun7 8년 전 1

ntopia 7년 전 0

h0ngjun7 7년 전 0

ntopia 7년 전 0

h0ngjun7 7년 전 0

h0ngjun7 7년 전 0

etaehyun4 7년 전 0

yukariko 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말