输出一行一个整数，表示最少需要的体力值。
刷水题有益身心健康。
SPFA:(这种的转移比后一种快很多，毕竟Dij要比较最小值)
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<cstdlib> 7 #include<vector> 8 using namespace std; 9 typedef long long ll; 10 typedef long double ld; 11 typedef pair<int,int> pr; 12 const double pi=acos(-1); 13 #define rep(i,a,n) for(int i=a;i<=n;i++) 14 #define per(i,n,a) for(int i=n;i>=a;i--) 15 #define Rep(i,u) for(int i=head[u];i;i=Next[i]) 16 #define clr(a) memset(a,0,sizeof(a)) 17 #define pb push_back 18 #define mp make_pair 19 #define fi first 20 #define sc second 21 #define pq priority_queue 22 #define pqb priority_queue <int, vector<int>, less<int> > 23 #define pqs priority_queue <int, vector<int>, greater<int> > 24 #define vec vector 25 ld eps=1e-9; 26 ll pp=1000000007; 27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;} 28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} 29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } 30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; } 31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1}; 32 ll read(){ ll ans=0; char last=‘ ‘,ch=getchar(); 33 while(ch<‘0‘ || ch>‘9‘)last=ch,ch=getchar(); 34 while(ch>=‘0‘ && ch<=‘9‘)ans=ans*10+ch-‘0‘,ch=getchar(); 35 if(last==‘-‘)ans=-ans; return ans; 36 } 37 const int N=200005; 38 #include<vector> 39 vector<int> vec_f[N],vec_t[N]; 40 #include<queue> 41 queue<int> Q; 42 ll dis[N],s[N],k[N]; 43 int r[N],vis[N]; 44 int main(){ 45 int n=read(),a_; 46 for (int i=1;i<=n;i++){ 47 s[i]=read(),k[i]=read(),r[i]=read(); 48 for (int j=1;j<=r[i];j++) { 49 a_=read(); 50 vec_f[i].pb(a_); 51 vec_t[a_].pb(i); 52 } 53 } 54 for (int i=1;i<=n;i++) 55 dis[i]=k[i],Q.push(i),vis[i]=1; 56 while (!Q.empty()){ 57 int u=Q.front(); Q.pop(); vis[u]=0; 58 int size=vec_t[u].size(); 59 ll sum=s[u]; 60 for (int j=0;j<r[u];j++) sum+=dis[vec_f[u][j]]; 61 if (sum>=dis[u]) continue; 62 dis[u]=sum; 63 for (int j=0;j<size;j++) 64 if (!vis[vec_t[u][j]]) Q.push(vec_t[u][j]),vis[vec_t[u][j]]=1; 65 } 66 printf("%lld",dis[1]); 67 return 0; 68 }
Dij:
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<cstdlib> 7 #include<vector> 8 using namespace std; 9 typedef long long ll; 10 typedef long double ld; 11 typedef pair<int,int> pr; 12 const double pi=acos(-1); 13 #define rep(i,a,n) for(int i=a;i<=n;i++) 14 #define per(i,n,a) for(int i=n;i>=a;i--) 15 #define Rep(i,u) for(int i=head[u];i;i=Next[i]) 16 #define clr(a) memset(a,0,sizeof(a)) 17 #define pb push_back 18 #define mp make_pair 19 #define fi first 20 #define sc second 21 #define pq priority_queue 22 #define pqb priority_queue <int, vector<int>, less<int> > 23 #define pqs priority_queue <int, vector<int>, greater<int> > 24 ld eps=1e-9; 25 ll pp=1000000007; 26 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;} 27 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} 28 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } 29 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; } 30 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1}; 31 ll read(){ ll ans=0; char last=‘ ‘,ch=getchar(); 32 while(ch<‘0‘ || ch>‘9‘)last=ch,ch=getchar(); 33 while(ch>=‘0‘ && ch<=‘9‘)ans=ans*10+ch-‘0‘,ch=getchar(); 34 if(last==‘-‘)ans=-ans; return ans; 35 } 36 const int N=200005; 37 struct node { 38 ll v; int i; 39 friend bool operator <(node a,node b){ 40 return a.v>b.v; 41 } 42 }; 43 #include<vector> 44 vector<int> vec_f[N],vec_t[N]; 45 #include<queue> 46 priority_queue<node> Q; 47 ll dis[N],s[N],k[N]; 48 int r[N],vis[N]; 49 int main(){ 50 int n=read(),a_; 51 for (int i=1;i<=n;i++){ 52 s[i]=read(),k[i]=read(),r[i]=read(); 53 for (int j=1;j<=r[i];j++) { 54 a_=read(); 55 vec_f[i].pb(a_); 56 vec_t[a_].pb(i); 57 } 58 } 59 for (int i=1;i<=n;i++) 60 dis[i]=k[i],Q.push((node){dis[i],i}); 61 while (!Q.empty()){ 62 int u=Q.top().i; Q.pop(); 63 if (vis[u]) continue; 64 int size=vec_t[u].size(); 65 for (int i=0;i<size;i++){ 66 int v=vec_t[u][i]; 67 if (vis[v]) continue; 68 ll sum=s[v]; 69 for (int j=0;j<r[v];j++) sum+=dis[vec_f[v][j]]; 70 if (sum<dis[v]){ 71 dis[v]=sum; Q.push((node){dis[v],v}); 72 } 73 } 74 vis[u]=1; 75 } 76 printf("%lld\n",dis[1]); 77 }
BZOJ 3875: [Ahoi2014&Jsoi2014]骑士游戏
原文：http://www.cnblogs.com/SXia/p/7694123.html
