글 읽기 - 76% 틀렸습니다. 어떤 반례가 있을까요? (주석있음)

shwjdgh3842 2년 전 1

int 대신 long long으로 바꿨는데도 이상하게 안되네요

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <queue>
#include <vector>
#include <string>
using namespace std;
int n, m, d, e;
const int inf = 2e9;
//인접 리스트 표현 
vector<pair<int, int>> adj[100001];
//순서대로 -거리,위치,고도
priority_queue<pair<pair<long long, long long>, long long>>pq;
//시작점부터 index까지의 최단거리 저장하는 배열
long long dist[100001];
//도착점부터 목적지까지의 최단거리 저장하는 배열
long long dist2[100001];
//각 지점의 높이를 저장하는 배열
int high[100001];

//src에서 출발해서 고도가 높아지는 방향으로 등산하는 루트
void fun(int src) {
	dist[src] = 0;
	pq.push({{ 0,src }, high[src]});
	while (!pq.empty()) {
		long long here = pq.top().first.second;
		long long cost = -pq.top().first.first;
		pq.pop();
		if (dist[here] < cost) {
			continue;
		}
		for (int i = 0; i < adj[here].size(); i++) {
			long long there = adj[here][i].first;
			long long nowcost = cost + adj[here][i].second;
			if (dist[there] > nowcost && high[here] < high[there]) {
				dist[there] = nowcost;
				pq.push({ { -nowcost,there }, high[there]});
			}
		}
	}
}

//하산하는 루트 역순
void fun2(int src) {
	dist2[src] = 0;
	pq.push({ { 0,src }, high[src] });
	while (!pq.empty()) {
		long long here = pq.top().first.second;
		long long cost = -pq.top().first.first;
		pq.pop();
		if (dist2[here] < cost) {
			continue;
		}
		for (int i = 0; i < adj[here].size(); i++) {
			long long there = adj[here][i].first;
			long long nowcost = cost + adj[here][i].second;
			if (dist2[there] > nowcost && high[here] < high[there]) {
				dist2[there] = nowcost;
				pq.push({ { -nowcost,there }, high[there] });
			}
		}
	}
}

void distmake() {
	for (int i = 1; i <= n; i++) {
		dist[i] = inf;
	}
}

void dist2make() {
	for (int i = 1; i <= n; i++) {
		dist2[i] = inf;
	}
}

int main() {
	cin >> n >> m >> d >> e;
	for (int i = 1; i <= n; i++) {
		cin >> high[i];
	}
	for (int j = 0; j < m; j++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ b,c });
		adj[b].push_back({ a,c });
	}
	distmake(), dist2make();
	fun(1), fun2(n);
	bool ispossible = false;
	long long ans = -inf;
	for (int i = 1; i < n; i++) {
		if (dist[i] != inf && dist2[i] != inf) {
			ispossible = true;
			long long val = e * high[i] - (dist[i] + dist2[i]) * d;
			if (val > ans) {
				ans = val;
			}
		}
	}

	if (!ispossible) {
		cout << "Impossible";
	}
	else {
		cout << ans;
	}
}

shwjdgh3842 2년 전 0

const long long inf = 2e14;로 바꾸니 되네요 ㅎ

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

문제

문제

출처

ICPC

76% 틀렸습니다. 어떤 반례가 있을까요? (주석있음)

shwjdgh3842 2년 전 1

shwjdgh3842 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말