有一个trick的地方：
当路劲数大于等于50左右，在题目要求的区间内：1 ≤ len ≤ ，一定有满足三角形的情况。具体的可以参考斐波那契数列，最坏的情况就是斐波那契的序列。所以大数据要这样过，在cn>=50左右直接返回Yes.
#include
#include
#include
#include
#include
#include
using namespace std; int f[][2],deep[]; vector
e[]; int c[60], cn; void dfs(int fa,int x,int d) { deep[x]=d; for(int i=0;i<(int)e[x].size();i+=2) { int y=e[x][i]; if(y==fa)continue; f[y][0]=x; f[y][1]=e[x][i+1]; dfs(x,y,d+1); } } int main() { int T,ca=1; // ifstream fin; // fin.open("aaa.txt"); // cout<
>T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); // fin>>n; for(int i=1;i<=n;i++)e[i].clear(); for(int i=1;i
>a>>b>>len; e[a].push_back(b); e[a].push_back(len); e[b].push_back(a); e[b].push_back(len); } dfs(0,1,0); f[1][0]=0; printf("Case #%d:\n", ca++); int m; scanf("%d",&m); // fin>>m; while(m--) { int s,t; cn=0; scanf("%d%d",&s,&t); if(s==1 || t==1) { int tmp=(s==1)?t:s; s=1; t=tmp; while(f[t][0]!=0) { c[cn++]=f[t][1]; t=f[t][0]; if(cn>=50)break; } } else { while(deep[t]>deep[s]) { c[cn++]=f[t][1]; t=f[t][0]; if(cn>=50)break; } while(deep[s]>deep[t]) { c[cn++]=f[s][1]; s=f[s][0]; if(cn>=50)break; } while(s!=t) { c[cn++]=f[s][1]; s=f[s][0]; c[cn++]=f[t][1]; t=f[t][0]; if(cn>=50)break; } } if(cn>=50){printf("Yes\n");continue;} sort(c,c+cn); int flag=0; for(int i=0;i+2
c[i+2]){ flag=1; break; } } if(flag)printf("Yes\n"); else printf("No\n"); } } return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/224770.html原文链接：https://javaforall.net
