最短路 DP
BZOJ題目傳送門
洛谷題目傳送門
很顯然有 f [ u ] = m i n ( k u , s u + ∑ f [ v ] ) f[u]=min(k_u,s_u+\sum f[v]) f[u]=min(ku,su+∑f[v])。但是這個是有後效性的,那麼就用spfa搞(也可以用類似拓撲的方法做)。每次更新一個點後把所有指向它的點都加到隊列裡更新即可。
代碼:
#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200005
#define F inline
using namespace std;
typedef long long LL;
struct edge{ int nxt,to; }ed[N*10];
int n,k,h1[N],h2[N]; LL a[N],b[N],d[N]; bool f[N];
queue <int> q;
F char readc(){
static char buf[100000],*l=buf,*r=buf;
if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
return l==r?EOF:*l++;
}
F LL _read(){
LL x=0; char ch=readc();
while (!isdigit(ch)) ch=readc();
while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc();
return x;
}
F LL spfa(){
for (int i=1;i<=n;i++) q.push(i),f[i]=true,d[i]=b[i];
while (!q.empty()){
int x=q.front(); q.pop(),f[x]=false; LL s=a[x];
for (int i=h1[x];i;i=ed[i].nxt) s+=d[ed[i].to];
if (s>=d[x]) continue; d[x]=s;
for (int i=h2[x],v;i;i=ed[i].nxt)
if (!f[v=ed[i].to]) q.push(v),f[v]=true;
}
return d[1];
}
#define add(h,x,y) ed[++k]=(edge){h[x],y},h[x]=k
int main(){
n=_read();
for (int i=1;i<=n;i++){
a[i]=_read(),b[i]=_read();
for (int m=_read(),x;m;m--)
x=_read(),add(h1,i,x),add(h2,x,i);
}
return printf("%lld\n",spfa()),0;
}