글 읽기 - 16681 등산-다익스트라 질문입니다.

opop20207 4년 전 0

시작점 0에서 각 위치까지 갈때 걸리는 최소거리, 시작점 N-1에서 각 위치까지 갈 때 걸리는 최소거리 계산해서

0,N-1 제외한 나머지 지점들에서 만족도를 계산했습니다.

맞게 짰다고 생각하는데 시간 초과가 60퍼대에서 나네요...

조언 부탁드립니다.

ㅡㅡ 수정했습니다.

70퍼대에서 틀렸다고 하네요.

ㅡㅡ 해결했습니다.

그냥 long long overflow문제였네요.

자세히 안본게 잘못이었던거같습니다...

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };
const int ddx[8] = { -1,-1,-1,0,0,1,1,1 };
const int ddy[8] = { -1,0,1,-1,1,-1,0,1 };
const int INF = 0x7fff5037;
const ll INF_LL = 0x7fffffffffffffff;
bool cidx(ll x, ll y, ll N, ll M) { return x >= 0 && x < N && y >= 0 && y < M; }
#define X first
#define Y second
#define pb push_back
#define sz(a) ((int)(a.size()))
#define sf1(a) cin >> a
#define sf2(a,b) cin >> a >> b
#define sf3(a,b,c) cin >> a >> b >> c
#define sf4(a,b,c,d) cin >> a >> b >> c >> d
#define sf5(a,b,c,d,e) cin >> a >> b >> c >> d >> e
#define pf1(a) cout << (a) << ' '
#define pf2(a,b) cout << (a) << ' ' << (b) << ' '
#define pf3(a,b,c) cout << (a) << ' ' << (b) << ' ' << (c) << ' '
#define pf4(a,b,c,d) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' '
#define pf5(a,b,c,d,e) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' ' << (e) << ' '
#define pfn0() cout << '\n'
#define pfn1(a) cout << (a) << '\n'
#define pfn2(a,b) cout << (a) << ' ' << (b) << '\n'
#define pfn3(a,b,c) cout << (a) << ' ' << (b) << ' ' << (c) << '\n'
#define pfn4(a,b,c,d) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << '\n'
#define pfn5(a,b,c,d,e) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' ' << (e) << '\n'
#define pfv(v) for(auto const &t : v) pfn1(t)
const int SIZE = 100100;
int N, M, D, E;
//N vertex, M edge, D HP / distance, E point / height
int height[SIZE];
vector<pair<int,ll>> adj[SIZE];
ll visit[SIZE];
ll visit2[SIZE];
bool chk[SIZE];
priority_queue<pii> pq;
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	sf4(N, M, D, E);
	for (int i = 0; i < N; i++) {
		sf1(height[i]);
	}
	for (int i = 0; i < M; i++) {
		int t1, t2;
		ll dis;
		sf3(t1, t2, dis);
		t1--, t2--;
		adj[t1].pb({ t2,dis });
		adj[t2].pb({ t1,dis });
	}
	pq.push({ 0,0 });
	fill(visit, visit + N, INF);
	fill(chk, chk + N, false);
	visit[0] = 0;
	while (!pq.empty()) {
		int ccost = -pq.top().X;
		int cx = pq.top().Y;
		pq.pop();
		if (chk[cx]) continue;
		chk[cx] = true;
		for (auto k : adj[cx]) {
			int nx = k.X;
			int ncost = ccost + k.Y;
			if (height[cx] < height[nx]) {
				if (visit[nx] > ncost) {
					visit[nx] = ncost;
					pq.push({ -ncost,nx });
				}
			}
		}
	}
	pq.push({ 0,N - 1 });
	fill(visit2, visit2 + N, INF);
	fill(chk, chk+N, false);
	visit2[N - 1] = 0;
	while (!pq.empty()) {
		int ccost = -pq.top().X;
		int cx = pq.top().Y;
		pq.pop();
		if (chk[cx]) continue;
		chk[cx] = true;
		for (auto k : adj[cx]) {
			int nx = k.X;
			int ncost = ccost + k.Y;
			if (height[cx] < height[nx]) {
				if (visit2[nx] > ncost) {
					visit2[nx] = ncost;
					pq.push({ -ncost,nx });
				}
			}
		}
	}
	ll res = -INF;
	for (int i = 1; i < N - 1; i++) {
		if (visit[i] == INF || visit2[i] == INF) continue;
		ll temp = height[i] * E - (visit[i] + visit2[i]) * D;
		res = max(res, temp);
	}
	if (res == -INF) pfn1("Impossible");
	else pfn1(res);
}

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

문제

문제

출처

ICPC

16681 등산-다익스트라 질문입니다.

opop20207 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말