记录编号	341107	评测结果	AAAAAAETETTTTTTTTTTT
题目名称	[NOIP 2011]观光公交	最终得分	30
用户昵称	GROWL GOOD BOYส็	是否通过	未通过
代码语言	C++	运行时间	13.858 s
提交时间	2016-11-07 13:49:25	内存使用	0.62 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10000+100;
int head[maxn];
struct edge
{
  int to,next;
}e[maxn*2];
int S[maxn],T[maxn],tim[maxn],ma[maxn],D[maxn];
int N,M,K,len;
int Ans=0x7fffffff;
void ADD(int x,int y)
{
     len++;
     e[len].to=y;
     e[len].next=head[x];
     head[x]=len;
}
void DFS(int pos,int N2,int dis,int ans)
{
     for(int t,i=head[pos];i;i=e[i].next)
     {
         t=e[i].to;
         ans+=dis-tim[t];    
     }
     if(ans>Ans)return;
     if(pos==N)
     {
       if(Ans>ans)Ans=ans;
       return;
     }
     if(dis<ma[pos])dis=ma[pos];
     for(int k=1;k<=N2;k++)
     {
       if(D[pos]-k>=0)DFS(pos+1,N2-k,dis+D[pos]-k,ans);
       else break;
     }
     DFS(pos+1,N2,dis+D[pos],ans);
}
int main()
{
    freopen("bus.in","r",stdin);
    freopen("bus.out","w",stdout);
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1;i<N;i++)scanf("%d",&D[i]);
    for(int i=1;i<=M;i++)scanf("%d%d%d",&tim[i],&S[i],&T[i]),ma[S[i]]=max(ma[S[i]],tim[i]),ADD(T[i],i);
    DFS(1,K,0,0);
    printf("%d",Ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}