记录编号	128098	评测结果	AAAAAAAAAA
题目名称	荒野迷路	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	1.379 s
提交时间	2014-10-16 20:49:55	内存使用	5.19 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <iterator>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct adj{
  int to,dist;
  adj (int to=0,int dist=0):to(to),dist(dist){}
};
//==============var declaration=================
const int MAXN=510;
bool win[MAXN][5010];
bool vis[MAXN][5010]; 
vector <adj> Edge[MAXN];
int n,m,k,T;
//==============function declaration============
bool drive(int x,int fuel);
//==============main code=======================
int main()
{  
  string FileName="fieldlost";//程序名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
  scanf("%d",&T);
  while (T--){
    scanf("%d%d%d",&k,&n,&m);
    For(i,1,n) Edge[i].clear();
    For(i,1,m){
      int s,e,len;
      scanf("%d%d%d",&s,&e,&len);
      Edge[s].push_back(adj(e,len));
      Edge[e].push_back(adj(s,len));
    }
    memset(vis,false,sizeof(vis));
    if (drive(1,k))
      printf("Yes!\n");
    else 
      printf("No!\n");
  }
  return 0;
}
//================fuction code====================
bool drive(int x,int fuel)//目前处于x，有fuel油，先开能否获胜 
{
  if (vis[x][fuel])
    return win[x][fuel];
  bool suc=false;
  int siz=Edge[x].size()-1;
  For(i,0,siz){
    adj &e=Edge[x][i];
    if (e.dist<=fuel){
      suc|=(!drive(e.to,fuel-e.dist));
      if (suc) return vis[x][fuel]=win[x][fuel]=true;
    }
  }
  vis[x][fuel]=true;
  return win[x][fuel]=suc;
}