글 읽기 - 지나간 도로의 개수 질문입니다..

simsimseo 8년 전 0

최대 비용 찾는 것은 어렵지 않게 구했는데

최대비용일 때 루트를 어떻게 효과적으로 세어야 할지 감이 안옵니다.

고수님들 힌트 좀 주시면 감사하겠습니다 ㅜㅜ

#define _CRT_SECURE_NO_WARNINGS
#define MAX_QUEUE_SIZE 100000
#include <iostream>
#include <vector>
using namespace std;

struct Vertex{
	vector<pair<int, int>> adj_list;
};
struct Node{
	int v;
	int cost;
};
Vertex city[10001];
Node queue[MAX_QUEUE_SIZE];
int front, rear;
int N, K, start, dest;
int max_cost;
void bfs()
{
	while (front != rear)
	{
		int v = queue[front].v;
		int cost = queue[front++].cost;
		front %= MAX_QUEUE_SIZE;
		if (v == dest){
			if (max_cost <= cost){
				max_cost = cost;
			}
		}
		int adj_size = city[v].adj_list.size();
		for (int i = 0; i < adj_size; i++){
			int next = city[v].adj_list[i].first;
			queue[rear].v = next;
			queue[rear++].cost = cost + city[v].adj_list[i].second;
			rear %= MAX_QUEUE_SIZE;
		}
	}
}
int main()
{
#ifdef _CONSOLE
	freopen("input.txt", "r", stdin);
#endif
	std::ios::sync_with_stdio(false);
	cin >> N >> K;
	for (int i = 0; i < K; i++){
		int a, b, c;
		cin >> a >> b >> c;
		city[a].adj_list.push_back(make_pair(b, c));
	}
	cin >> start >> dest;
	queue[rear].v = start;
	queue[rear++].cost = 0;
	bfs();
	cout << max_cost << "\n";
}

yohan5050 8년 전 5

각 도시까지의 최대비용을 알 수 있잖아요? 그것을 따로 저장해놓으시고,

도착도시부터 시작해서 거꾸로 탐색을 하시면서 각 도시까지의 최대비용과 비교해보시면

최대비용이 나오기 위해서 어떤 길들을 거쳐 도착도시에 도착했는지 알 수 있어요.

simsimseo 8년 전 1

감사합니다!!덕분에 풀었습니다!!

simsimseo 8년 전 2

결국 제출만 53회 했습니다 정말 감사합니다 ㅋㅋ

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

문제

문제

출처

ICPC

지나간 도로의 개수 질문입니다..

simsimseo 8년 전 0

yohan5050 8년 전 5

simsimseo 8년 전 1

simsimseo 8년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말