글 읽기 - 어떤부분에서 잘못 된걸까요?

smu201111192 7년 전 0

정올 데이터로 비교해보니 정말 근소한 차이로 틀리고 있던데.

모가 문제인지 잘 모르겠습니다.

아파트 단지 a,b,c의 대쇼비교가 잘못 된걸까요?

도와주세요 고수님들ㅠ

#include <queue>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
struct edge{
	int to, cost;
	edge(int to, int cost){
		this->to = to;
		this->cost = cost;
	}
};
vector<int> tree;
int a, b, c, n, m;
int dist[150001][3];
vector<vector<edge> > adj;
struct node{
	int a, b, c, index;
	bool operator < (const node nd)const{
		if (a != nd.a)return a < nd.a;
		else if (b != nd.b)return b < nd.b;
		else return c < nd.c;
	}
}nd[150001];
void dy(int s, int dN){
	for (int i = 0; i <= n; i++)dist[i][dN] = 1e9;
	dist[s][dN] = 0;
	priority_queue<pair<int, int> > q;
	q.push(make_pair(0, s));
	while (!q.empty()){
		int cost = -q.top().first;
		int here = q.top().second;
		q.pop();
		if (dist[here][dN] < cost)continue;
		for (int i = 0; i < adj[here].size(); i++){
			edge &e = adj[here][i];
			if (dist[e.to][dN]>cost + e.cost){
				dist[e.to][dN] = cost + e.cost;
				q.push(make_pair(-dist[e.to][dN], e.to));
			}
		}
	}
}
int update(int node, int s, int e, int pos, int value){
	if (pos<s || pos>e)return tree[node];
	if (s == e)return tree[node] = value;
	int mid = (s + e) / 2;
	return tree[node] = min(update(node * 2, s, mid, pos, value), update(node * 2 + 1, mid + 1, e, pos, value));
}
int query(int node, int s, int e, int st, int ed){
	if (e<st || s>ed)return 1e9;
	if (s >= st && e <= ed)return tree[node];
	int mid = (s + e) / 2;
	return tree[node] = min(query(node * 2, s, mid, st, ed), query(node * 2 + 1, mid + 1, e, st, ed));
}
int main(){
	bool check[150001] = { 0, };
	map<int, int> mp;
	adj.clear();
	scanf("%d", &n);
	adj.resize(n + 10);
	scanf("%d %d %d", &a, &b, &c);
	int edgeN;
	scanf("%d", &edgeN);
	for (int i = 0; i < edgeN; i++){
		int from, to, cost;
		scanf("%d %d %d", &from, &to, &cost);
		adj[from].push_back(edge(to, cost));
		adj[to].push_back(edge(from, cost));
	}
	dy(a, 0), dy(b, 1), dy(c, 2);
	for (int i = 1; i <= n; i++){
		mp[dist[i][1]] = -1;
	}
	int cnt = 1;
	for (auto it = mp.begin(); it != mp.end(); it++){
		it->second = cnt++;
	}
	for (int i = 1; i <= n; i++){
		nd[i].a = dist[i][0];
		nd[i].b = mp[dist[i][1]];
		nd[i].c = dist[i][2];
		nd[i].index = i;
	}
	cnt--;
	tree.resize(6 * cnt);
	for (int i = 0; i < 5 * cnt; i++)tree[i] = 1e9;
	sort(nd + 1, nd + 1 + n);;
	scanf("%d", &m);
	for (int i = 1; i <= n; i++){
		int idx = nd[i].index;
		int b = nd[i].b; 
		int c = nd[i].c;
		int cand = query(1, 1, cnt, 1, b);
		if (cand <c){
			check[idx] = 1;
		}
		else{
			update(1, 1, cnt, b, c);
		}
	}

	for (int i = 0; i < m; i++){
		int num; scanf("%d", &num);
		if (!check[num])printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

dbgksdl00 1년 전 0

오래 지난 글이긴 하지만 특정 지점에 접근하는 거리가 동일할 수 있습니다.

해당 상황에 대한 예외처리가 없어 발생하는 문제 같네요.

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

문제

문제

출처

ICPC

어떤부분에서 잘못 된걸까요?

smu201111192 7년 전 0

dbgksdl00 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말