luoguP2991 [USACO10OPEN]水滑梯Water Slides

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=4e5+5;
 4 const long long INF=((1ll*1)<<60);
 5 struct A
 6 {
 7     int v,w,next;
 8 }e[maxn];
 9 int tot,head[maxn];
10 int n,m,k;
11 long long f[50005][15];
12 template<class t>void red(t &x)
13 {
14     int w=1;
15     x=0;
16     char ch=getchar();
17     while(ch>'9'||ch<'0')
18     {
19         if(ch=='-')
20             w=-1;
21         ch=getchar(); 
22     }
23     while(ch>='0'&&ch<='9')
24     {
25         x=(x<<3)+(x<<1)+ch-'0';
26         ch=getchar();
27     } 
28     x*=w;
29 } 
30 void input()
31 {
32     freopen("input.txt","r",stdin);
33 }
34 void add(int x,int y,int z)
35 {
36     e[++tot].v=y;
37     e[tot].w=z;
38     e[tot].next=head[x];
39     head[x]=tot;
40 }
41 void read()
42 {
43     red(n);
44     red(m);
45     red(k);
46     int x,y,z;
47     for(int i=1;i<=m;++i)
48     {
49         red(x);
50         red(y);
51         red(z);
52         add(x,y,z);
53     }
54 }
55 long long dfs(int pos,int u)
56 {
57     if(u==n)
58         return 0;
59     if(f[pos][u])
60         return f[pos][u];
61     long long maxn=-1,minn=INF;
62     for(int i=head[u];i;i=e[i].next)
63     {
64         int v=e[i].v;
65         int w=e[i].w;
66         maxn=max(maxn,dfs(pos,v)+w);
67     }
68     if(pos)
69     {
70         for(int i=head[u];i;i=e[i].next)
71         {
72             int v=e[i].v;
73             int w=e[i].w;
74             minn=min(minn,dfs(pos-1,v)+w);
75         }
76     }
77     f[pos][u]=min(maxn,minn);
78     return f[pos][u];    
79 }
80 void work()
81 {
82     printf("%lld
",dfs(k,1));    
83 }
84 int main()
85 {
86     input();
87     read();
88     work();
89     return 0;
90 }

数组开反暴死30

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=4e5+5;
 4 const long long INF=((1ll*1)<<60);
 5 struct A
 6 {
 7     int v,w,next;
 8 }e[maxn];
 9 int tot,head[maxn];
10 int n,m,k;
11 long long f[15][50005];
12 template<class t>void red(t &x)
13 {
14     int w=1;
15     x=0;
16     char ch=getchar();
17     while(ch>'9'||ch<'0')
18     {
19         if(ch=='-')
20             w=-1;
21         ch=getchar(); 
22     }
23     while(ch>='0'&&ch<='9')
24     {
25         x=(x<<3)+(x<<1)+ch-'0';
26         ch=getchar();
27     } 
28     x*=w;
29 } 
30 void input()
31 {
32     freopen("input.txt","r",stdin);
33 }
34 void add(int x,int y,int z)
35 {
36     e[++tot].v=y;
37     e[tot].w=z;
38     e[tot].next=head[x];
39     head[x]=tot;
40 }
41 void read()
42 {
43     red(n);
44     red(m);
45     red(k);
46     int x,y,z;
47     for(int i=1;i<=m;++i)
48     {
49         red(x);
50         red(y);
51         red(z);
52         add(x,y,z);
53     }
54 }
55 long long dfs(int pos,int u)
56 {
57     if(u==n)
58         return 0;
59     if(f[pos][u])
60         return f[pos][u];
61     long long maxn=-1,minn=INF;
62     for(int i=head[u];i;i=e[i].next)
63     {
64         int v=e[i].v;
65         int w=e[i].w;
66         maxn=max(maxn,dfs(pos,v)+w);
67     }
68     if(pos)
69     {
70         for(int i=head[u];i;i=e[i].next)
71         {
72             int v=e[i].v;
73             int w=e[i].w;
74             minn=min(minn,dfs(pos-1,v)+w);
75         }
76     }
77     f[pos][u]=min(maxn,minn);
78     return f[pos][u];    
79 }
80 void work()
81 {
82     printf("%lld
",dfs(k,1));    
83 }
84 int main()
85 {
86     input();
87     read();
88     work();
89     return 0;
90 }

100