四川重庆是哪个省,网站运营和seo的区别,河北省建设工程,山东省工程建设信息网链接#xff1a;
1462. 课程表 IV
题意
一个pairint,int表示a是b的前置
进行n次查询#xff0c;查询q是否是p的前置#xff08;可以不是直接前置#xff09;
解#xff1a;
就是要把01、12、13这种能转换出02、03#xff0c;弗洛伊德即可
无环无负权
实际…链接
1462. 课程表 IV
题意
一个pairint,int表示a是b的前置
进行n次查询查询q是否是p的前置可以不是直接前置
解
就是要把01、12、13这种能转换出02、03弗洛伊德即可
无环无负权
实际代码
#includebits/stdc.h
using namespace std;
vectorbool checkIfPrerequisite(int numCourses, vectorvectorint prerequisites, vectorvectorint queries)
{vectorvectorintedges(numCourses3,vectorint(numCourses3));for(auto prerequisite:prerequisites) edges[prerequisite[0]][prerequisite[1]]1;for(int i0;inumCourses;i){for(int j0;jnumCourses;j){if(edges[i][j]0) edges[i][j]0X3f3f3f3f;}}for(int t0;tnumCourses;t){for(int i0;inumCourses;i){for(int j0;jnumCourses;j){if(edges[i][t]edges[t][j]edges[i][j]){edges[i][j]1;}}}}vectorboolans;for(auto querie:queries){if(edges[querie[0]][querie[1]]0x3f3f3f3f) ans.push_back(true);else ans.push_back(false);}return ans;
}限制
2 numCourses 1000 prerequisites.length (numCourses * (numCourses - 1) / 2)prerequisites[i].length 20 ai, bi n - 1ai ! bi每一对 [ai, bi] 都 不同先修课程图中没有环。1 queries.length 1040 ui, vi n - 1ui ! vi
