글 읽기 - 1486 등산로 무엇이 문제인지 모르겠습니다 ㅠㅠ

cleverdevk 3년 전 0

갈때 올때 두번의 다익스트라로 해서 cost + backcost <= D 인것으로 구하는데

어떤부분이 틀렸는지 모르겠습니다 ㅠㅠ

도와주세요. ㅠㅠ

// 05.31. 9:54 ~ 
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <tuple>
#include <cstring>
#include <string>

#define INF 1000000000

using namespace std;

int n, m, t, d;
int mp[26][26];

int dr[] = { 0,1,0,-1 };
int dc[] = { 1,0,-1,0 };

int maxVal = 0;

vector<tuple<int, int ,int>> way[26][26], backway[26][26];
int cost[26][26];
int backcost[26][26];


void setBackCost()

{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			backcost[i][j] = INF;
		}
	}
}

void setCost()
{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cost[i][j] = INF;
		}
	}
}


void dijkstraReverse(int startRow, int startCol)
{
	setBackCost();
	backcost[startRow][startCol] = 0;
	priority_queue<tuple<int, int, int>> q;
	q.push({ 0,startRow,startCol });

	while (!q.empty()) {
		int curCost, curRow, curCol;
		tie(curCost, curRow, curCol) = q.top();
		curCost = -curCost;
		q.pop();

		for (int i = 0; i < backway[curRow][curCol].size(); i++) {
			int nextRow, nextCol, nextCost;
			tie(nextCost, nextRow, nextCol) = backway[curRow][curCol][i];

			if (backcost[nextRow][nextCol] > curCost + nextCost) {
				backcost[nextRow][nextCol] = curCost + nextCost;
				q.push({ -backcost[nextRow][nextCol], nextRow, nextCol });
			}
		}
	}
}

void dijkstra(int startRow, int startCol)
{
	setCost();
	cost[startRow][startCol] = 0;
	priority_queue<tuple<int, int, int>> q;
	q.push({ 0,startRow,startCol });

	while (!q.empty()) {
		int curCost, curRow, curCol;
		tie(curCost, curRow, curCol) = q.top();
		curCost = -curCost;
		q.pop();

		for (int i = 0; i < way[curRow][curCol].size(); i++) {
			int nextRow, nextCol, nextCost;
			tie(nextCost, nextRow, nextCol) = way[curRow][curCol][i];

			if (cost[nextRow][nextCol] > curCost + nextCost) {
				cost[nextRow][nextCol] = curCost + nextCost;
				q.push({ -cost[nextRow][nextCol], nextRow, nextCol });
			}
		}
	}
}

void updateHighestHill()
{
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (cost[i][j] + backcost[i][j] <= d) {
				maxVal = max(maxVal, mp[i][j]);
			}
		}
	}
}

int main()
{
	cin >> n >> m >> t >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			if (c >= 'A' && c <= 'Z') {
				mp[i][j] = c - 'A';
			}
			else {
				mp[i][j] = c - 'a' + 26;
			}
		}
	}

	// way 배열 채워주기 (인접리스트)
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int row = i;
			int col = j;
			int height = mp[i][j];
			for (int k = 0; k < 4; k++) {
				int nrow = row + dr[k];
				int ncol = col + dc[k];

				if (nrow < 0 || ncol < 0 || nrow >= n || ncol >= m) continue;

				int nheight = mp[nrow][ncol];

				//높이차
				int diff = abs(height - nheight);
				// 높이 차가 T보다 크면 못간다.
				if (diff > t) continue;
				// 높이에 따른 cost 
				if (height > nheight) {
					way[row][col].push_back(make_tuple(1, nrow, ncol));
					backway[row][col].push_back(make_tuple(diff*diff, nrow, ncol));
				}
				else if (height < nheight) {
					way[row][col].push_back(make_tuple(diff*diff, nrow, ncol));
					backway[row][col].push_back(make_tuple(1, nrow, ncol));
				}
				else {
					way[row][col].push_back(make_tuple(1, nrow, ncol));
					backway[row][col].push_back(make_tuple(1, nrow, ncol));
				}

			}
		}
	}


	dijkstra(0,0);
	dijkstraReverse(0, 0);
	maxVal = mp[0][0];
	updateHighestHill();

	cout << maxVal;


	return 0;
}

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

문제

문제

출처

ICPC

1486 등산로 무엇이 문제인지 모르겠습니다 ㅠㅠ

cleverdevk 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말