记录编号	326335	评测结果	AWWWTTTETT
题目名称	2507.零食店	最终得分	10
用户昵称	GROWL GOOD BOYส็	是否通过	未通过
代码语言	C++	运行时间	5.190 s
提交时间	2016-10-21 07:25:00	内存使用	0.45 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

const int maxn=100+10;

int N,M,Q,S,C,D,Cnt,len;

int flag[maxn],Ans=0;

int head[maxn],data[maxn];

struct edge
{
       int dis,to,next;
}e[maxn*maxn];

void ADD(int x,int y,int dis)
{
     len++;
     e[len].to=y;
     e[len].next=head[x];
     e[len].dis=dis;
     head[x]=len;
}

void DFS(int x,int tot,int dis)
{
     //flag[x]=Cnt;
     //printf("++   %d\n",x);
     Ans=max(Ans,tot);
     if(data[x]>C&&!tot)
     {
     Ans=max(Ans,tot);
     return;
     }
     for(int t,i=head[x];i;i=e[i].next)
     {
      t=e[i].to;
      if(flag[t]!=Cnt&&e[i].dis+dis<=D)
      { 
         //printf("t  %d\n",t);
         flag[t]=Cnt;
         DFS(t,tot+1,dis+e[i].dis);
         flag[t]=Cnt-1;         
      }            
     }
}

int main()
{
    freopen("snackstore.in","r",stdin);
    freopen("snackstore.out","w",stdout); 
    scanf("%d%d%d",&N,&M,&Q);
    for(int i=1;i<=N;i++)scanf("%d",&data[i]);
    for(int x,y,z,i=1;i<=M;i++)
    {
         scanf("%d%d%d",&x,&y,&z);
         ADD(x,y,z);
         ADD(y,x,z); 
    }    
    for(int i=1;i<=Q;i++)
    {
      scanf("%d%d%d",&S,&C,&D);
      Ans=1;
      ++Cnt;
      flag[S]=Cnt;
      DFS(S,1,0);
      printf("%d\n",Ans-1);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}