로곡P4042 [AHOI 2014/JSOI 2014] 기사 게임
제목의 뜻
\(n\)개의 몬스터가 있습니다.\(k\)의 대가를 소모하여 한 몬스터를 소멸하거나\(s\)의 대가를 소모하여 다른 몬스터나 여러 개의 새로운 몬스터로 변신시켜 몬스터를 소멸할 수 있습니다.\(1\)의 최소 대가를 구합니다
사고의 방향
\(DP\) + 최단 회로
요 며칠 동안 만든 첫 번째 자기가 풀 수 있는 문제...
보아하니\(\texttt{DP}\)인 것 같은데, 잠시 진지하게 생각해 봐도 다음과 같은 상태를 설계할 수 있을 거라고 생각하지 않는다.
\(f[i]\)를\(i\)를 없애는 데 필요한 최소 대가로 설정하면
\[f[i]=\min(f[i], s[i]+\sum\limits_{to_i} f[to_i])\]
여기서\(to\)는\(i\) 점의 후계를 나타냅니다.
\(f\)의 전환 간에 상호 간섭이 있으므로 최단 회로 처리
먼저 양방향 테두리를 만들어서 편리하게 옮긴 다음에\(\texttt{SPFA}\)(죽으면'다원'최단로를 구하면 됩니다.
처음부터 어떤 괴물을 쳐야 할지 모르니 아예 다 입대하고 업데이트하면 돼
\(ps:\) 2년\(\text{OI}\) 한 번도 헛되이 보내지 않고\(long\long\) 조상을 만나지 않는다.
코드
/*
Author:Loceaner
*/
#include
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int A = 2e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
queue Q;
vector v1[A], v2[A];
int n, m, ord[A], mag[A]/* s[i],k[i]*/, vis[A];
inline void ZDL() {
for (int i = 1; i <= n; i++) Q.push(i), vis[i] = 1;
while (!Q.empty()) {
int x = Q.front(); Q.pop(), vis[x] = 0;
int res = ord[x];
for (int i = 0; i < (int)v1[x].size(); i++) res += mag[v1[x][i]];
if (res < mag[x]) {
mag[x] = res;
for (int i = 0; i < (int)v2[x].size(); i++)
if (!vis[v2[x][i]]) Q.push(v2[x][i]), vis[v2[x][i]] = 1;
}
}
}
signed main() {
n = read();
for (int i = 1, k; i <= n; i++) {
ord[i] = read(), mag[i] = read(), k = read();
while (k--) {
int x = read();
v1[i].push_back(x), v2[x].push_back(i);
}
}
ZDL();
cout << mag[1] << '
';
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
