http://acm.timus.ru/problem.aspx?space=1&num=1227
刚开始理解错题意了呀 开始和结束点可以在路上 并不一定在节点上
如果有环 YES
如果没有环 任意树中最长路径满足条件 YES
否则 NO
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<vector> #include<map> #include<queue> #include<stack> #include<cmath> #define LL long long //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const int N=150; int head[N],I; struct node { int j,d,next; }side[N*N]; bool visited[N]; int n,m,S; void Add(int i,int j,int d) { side[I].j=j; side[I].d=d; side[I].next=head[i]; head[i]=I++; } bool dfs(int x,int pre,int s) { if(visited[x]||s>=S) return true; visited[x]=true; for(int t=head[x];t!=-1;t=side[t].next) { if(side[t].j==pre) {pre=-1;continue;} if(dfs(side[t].j,x,s+side[t].d)) return true; } return false; } int main() { //freopen("data.txt","r",stdin); while(cin>>n>>m>>S) { memset(head,-1,sizeof(head)); I=0; while(m--) { int i,j,d; cin>>i>>j>>d; Add(i,j,d); Add(j,i,d); } bool k=false; for(int i=1;i<=n;++i) { memset(visited,false,sizeof(visited)); if(dfs(i,-1,0)) {k=true;break;} } if(k) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }