首页 > 代码库 > wustoj 1318 区间的连通性 (最短路)
wustoj 1318 区间的连通性 (最短路)
floyd求最短路判断图的联通性。
注意图是有向图。。。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; struct node { int x,y,id; }edge[205]; int dis[205][205]; int main() { int c,T,n,a,b,op; while(scanf("%d",&T)!=EOF) { memset(dis,0,sizeof(dis)); memset(edge,0,sizeof(edge)); c = 1; for(int i=1;i<=T;i++) { scanf("%d%d%d",&op,&a,&b); if(op==1) { edge[c].x = a; edge[c].y = b; edge[c].id = c; for(int k=1;k<c;k++) { if((edge[k].x<a && a<edge[k].y) || (edge[k].x<b && b<edge[k].y)) dis[c][k]=1; if((a<edge[k].x && edge[k].x<b) || (a<edge[k].y && edge[k].y<b)) dis[k][c]=1; } c++; } else { if(dis[a][b]) printf("YES\n"); else { for(int x=1;x<c;x++) { for(int j=1;j<c;j++) { for(int l=1;l<c;l++) if(dis[j][x] && dis[x][l]) dis[j][l]=1; } } if(dis[a][b]) printf("YES\n"); else printf("NO\n"); } } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。