글 읽기 - C++/ 반례가 있을까요??

pppp1923 4년 전 0

테스트케이스랑 질문글의 반례도 잘 통과합니다.

무엇이 문제일까요.. ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Edge {
	int to;
	int cost;
	Edge(int to, int cost) : to(to), cost(cost) {}
};

vector<Edge> a[101];
int seonghadist[101];
bool seonghacheck[101];
int jihyeondist[101];
bool jihyeoncheck[101];
int inf = 2147483647;

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		a[x].push_back(Edge(y, z));
		a[y].push_back(Edge(x, z));
	}
	int seongha, jihyeon;
	cin >> jihyeon >> seongha;

	for (int i = 1; i <= n; i++) {
		seonghadist[i] = inf;
		jihyeondist[i] = inf;
	}

	//성하부터 모든 점의 최단거리
	seonghadist[seongha] = 0;
	priority_queue<pair<int, int>> q;
	q.push(make_pair(0, seongha));
	while (!q.empty()) {
		auto p = q.top();
		q.pop();
		int x = p.second;
		if (seonghacheck[x] == true) continue;
		seonghacheck[x] = true;
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i].to;
			if (seonghadist[y] > seonghadist[x] + a[x][i].cost) {
				seonghadist[y] = seonghadist[x] + a[x][i].cost;
				q.push(make_pair(-seonghadist[y], y));
			}
		}
	}

	//지현부터 모든 점의 최단거리
	jihyeondist[jihyeon] = 0;
	q.push(make_pair(0, jihyeon));
	while (!q.empty()) {
		auto p = q.top();
		q.pop();
		int x = p.second;
		if (jihyeoncheck[x] == true) continue;
		jihyeoncheck[x] = true;
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i].to;
			if (jihyeondist[y] > jihyeondist[x] + a[x][i].cost) {
				jihyeondist[y] = jihyeondist[x] + a[x][i].cost;
				q.push(make_pair(-jihyeondist[y], y));
			}
		}
	}


	//1,2,3,4 조건 시작
	int sum = inf;
	int min = inf;
	int ans = -1;
	for (int k = 1; k <= n; k++) { //약속장소 k라면
		if (k == seongha || k == jihyeon) continue; //1번조건
		int temp = seonghadist[k] + jihyeondist[k];
		if (sum < temp) continue; //2번 조건
		if (seonghadist[k] < jihyeondist[k]) continue; //3번조건
		sum = temp;
		if (min > jihyeondist[k]) {
			min = jihyeondist[k];
			ans = k;
		}
	}

	cout << ans << "\n";

	return 0;
}

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

문제

문제

출처

ICPC

C++/ 반례가 있을까요??

pppp1923 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말