思路：
1.先建图
2.然后对每一种序列都处理一次，然后看看这个序列到起点的距离是不是逐渐递增的
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int h[N],e[2 * N],w[2 * N],ne[2 * N],idx; int xu[N]; bool st[N];; typedef pair<int,int> PII; int d[N]; void add(int a,int b,int c){ w[idx] = c,e[idx] = b,ne[idx] = h[a],h[a] = idx++; } void dijkstra(int u) { memset(st,false,sizeof st); priority_queue<PII,vector<PII>,greater<PII>>q; q.push({0,u}); d[u] = 0; while(q.size()) { auto t = q.top(); q.pop(); int distance = t.first,ver = t.second; if(st[ver]) continue; st[ver] = true; for(int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if(d[j] > distance + w[i]) { d[j] = distance + w[i]; q.push({d[j],j}); } } } } int main() { ios::sync_with_stdio(false),cin.tie(0); memset(h,-1,sizeof h); int n,m; cin >> n >> m; for(int i = 1; i <= m; i ++) { int a,b,c; cin >>a >> b >> c; add(a,b,c); add(b,a,c); } int k; cin >>k; while(k --) { int flag = 0; memset(d,0x3f,sizeof d); for(int i = 1; i <= n; i ++) cin >> xu[i]; dijkstra(xu[1]); for(int i = 1; i < n; i ++) if(d[xu[i + 1]] < d[xu[i]]) { flag = 1; break; } if(flag) puts("No"); else puts("Yes"); } return 0; }
