글 읽기 - 이 코드가 왜 틀렸을까용??

devbelly 3년 전 0

해당코드가 왜 틀렸는지 잘 모르겠습니다. ㅠㅠㅠ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
int n, m, u, v, c;
vector<int> gascost;
vector<vector<p>> adj;
ll cache[2501][2501]; 
ll solve(int here, int mincost) { // 현재위치 here에서 사용가능한 주유소가격 mincost일때 
	if (here == n) return 0;      // n까지 도달하기 위해 지불하는 최소 가격!

	ll& ret = cache[here][mincost];
	if (ret != -1) return ret;
	ret = LLONG_MAX / 10; 
	for (auto [there, dist] : adj[here])
		ret = min(ret, solve(there, min(mincost, gascost[there])) + mincost * dist);

	return ret;
}
int main() {
	cin.tie(NULL);cout.tie(NULL);
	ios::sync_with_stdio(false);

	memset(cache, -1, sizeof(cache));

	cin >> n >> m;
	gascost = vector<int>(n + 1);
	adj.resize(n + 1);
	for (int i = 1;i <= n;++i)
		cin >> gascost[i];

	while (m--) {
		cin >> u >> v >> c;
		adj[u].emplace_back(v, c);
		adj[v].emplace_back(u, c);
	}
	cout << solve(1, gascost[1]);


	return 0;
}

devbelly 3년 전 1

사이클이 존재한 상태에서 dp를 바로 쓰면 안됩니다. ㅎㅎ 모든 dp는 dag로 표현이 가능하다고 하네요

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

문제

문제

출처

ICPC

이 코드가 왜 틀렸을까용??

devbelly 3년 전 0

devbelly 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말