洛谷 P4042 [AHOI2014/JSOI2014]骑士游戏

题意

有(n)个怪物，可以消耗(k)的代价消灭一个怪物或者消耗(s)的代价将它变成另外一个或多个新的怪物，求消灭怪物(1)的最小代价

思路

(DP)+最短路

这几天做的第一道自己能(yy)出来的题……

看起来像是个( exttt{DP})，认真思考一会儿也不难想到可以设计如下状态

设(f[i])为消灭(i)所需的最小代价，那么有

[f[i]=min(f[i], s[i]+sumlimits_{to_i} f[to_i]) ]

其中(to)表示(i)点的后继

因为(f)的转移之间相互干涉，所以用最短路处理

先建双向边，方便之后转移，然后用( exttt{SPFA})（它死了求"多源"最短路就好了

因为不知道一开始应该打哪个怪物，所以干脆全都入队、全部更新就好了

(ps:)两年( ext{OI})一场空，不开(long long)见祖宗

代码

/*
Author:Loceaner
*/
#include <queue>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#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 <int> Q;
vector <int> 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;
}