[Acwing] 343.排序 floyd传递闭包

前言

处理过程很细致,值得二刷 传送门 :

思路

对于每一次读入我们都用 f l o y d floyd floyd传递闭包,也就是实现 d i s t [ i ] [ j ] & & d i s t [ j ] [ k ] 推 出 d i s t [ i ] [ k ] dist[i][j]\&\&dist[j][k] 推出 dist[i][k] dist[i][j]&&dist[j][k]推出dist[i][k]

同时对于每一次输入之后,我们都需要判断是否所有边都联通也就是关系是否明确

最后输出关系的时候,我们需要枚举整个图反着退出最小的一个点,并且标记

CODE

//传递闭包 
void floyd()
{
	memcpy(d,g,sizeof d);
	
	for(int k = 0 ;k