一、题目描述：
给你一个 n 个点，m 条边的无向图，点带权，起点可任意选择。
每走过一个新的点，你的能力值会 +1 。一开始你的能力值为 0 。
你只能经过点权小于等于你能力值的点。每条边，每个点都可以经过无限次，问能否走遍整个图。
如果可以，输出 "YES" 。否则输出 "NO" 。有 t组数据，保证 n 的总和，m 的总和都不超过 2e5 ，t <= 1e3 。
二、做题思路：
很明显，你只能选择点权为 0 的点作为起点。枚举每个点权为 0 的点，跑一边 dij ，时间复杂度 O(n*nlogm)，显然超时。
考虑优化，之前已经访问过的点再用作起点肯定不优（这里不做解释）。用一个 vis 数组标一下。
每次 dij 不能 O(n) 的初始化，判定一个点 u 这一轮是否访问过的时候可以判 if (vis[u]==s)，其中 s 为起点。
现在时间复杂度已经是 O(nlogm) 了。复杂度不好直接说明，放个图：
假设一开始枚举的点是中间那个 0 ，一共可以拓展到 4 个点。周围被点权较大的点所包围，无法再拓展。
如果重复拓展到这几个点，那么一定是经过了点权较大的点，此时经过的点一定大于 4 个 ，才能通过点权较大的点。
由此可以发现，总拓展点数最大为 n+n/2+n/4+n/8+...，小于等于 2n 。时间复杂度最差 O(2nlogm)，可以通过。
三、完整代码：
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 #define N 200010 5 using namespace std; 6 int T,n,m,u1,v1,now,c[N],vis[N]; 7 struct EDGE{ 8 int v,nxt; 9 }edge[N*2]; 10 int head[N],cnt; 11 void add(int u,int v) 12 { 13 edge[++cnt].v=v; 14 edge[cnt].nxt=head[u]; 15 head[u]=cnt; 16 } 17 struct node{ 18 int pos,dis; 19 bool operator < (const node &t)const{ 20 return t.dis<dis; 21 } 22 }; 23 priority_queue <node> q; 24 int dij(int s) 25 { 26 while(!q.empty()) 27 q.pop();q.push({s,0});now=0; 28 while(!q.empty()) 29 { 30 int u=q.top().pos;q.pop(); 31 if(vis[u]==s) continue;vis[u]=s; 32 if(now<c[u]) return 0; now++; 33 for(int i=head[u];i!=-1;i=edge[i].nxt) 34 q.push({edge[i].v,c[edge[i].v]}); 35 } 36 return now==n; 37 } 38 void solve() 39 { 40 cin>>n>>m;cnt=0; 41 for(int i=1;i<=n;i++) 42 { 43 cin>>c[i]; 44 head[i]=-1,vis[i]=0; 45 } 46 for(int i=1;i<=m;i++) 47 { 48 cin>>u1>>v1; 49 add(u1,v1),add(v1,u1); 50 } 51 for(int i=1;i<=n;i++) 52 if(!c[i]&&!vis[i]&&dij(i)) 53 { 54 cout<<"YES"<<'\n'; 55 return ; 56 } 57 cout<<"NO"<<'\n'; 58 } 59 int main() 60 { 61 ios::sync_with_stdio(false); 62 cin.tie(0);cout.tie(0); 63 cin>>T; 64 for(int i=1;i<=T;i++) 65 solve(); 66 return 0; 67 }
四、写题心得：
这个题写起来不难，就是时间复杂度难以证明。不过自己花了这么多时间证出来了（头一次配了图 ! ），也是真的很高兴。拜拜！