微网站免费模板,管理网络的网站,汕头市城市建设开发总公司,网站建设多少钱一个站题目描述 在古老的魔兽传说中#xff0c;有两个军团#xff0c;一个叫天灾#xff0c;一个叫近卫。在他们所在的地域#xff0c;有n个隘口#xff0c;编号为1..n#xff0c;某些隘口之间是有通道连接的。其中近卫军团在1号隘口#xff0c;天灾军团在n号隘口。某一天有两个军团一个叫天灾一个叫近卫。在他们所在的地域有n个隘口编号为1..n某些隘口之间是有通道连接的。其中近卫军团在1号隘口天灾军团在n号隘口。某一天天灾军团的领袖巫妖王决定派兵攻打近卫军团天灾军团的部队如此庞大甚至可以填江过河。但是巫妖王不想付出不必要的代价他想知道在不修建任何通道的前提下部队是否可以通过隘口及其相关通道到达近卫军团展开攻击如果可以的话最少需要经过多少通道。由于n的值比较大n1000于是巫妖王找到了擅长编程的你 _请你帮他解决这个问题否则就把你吃掉变成他的魔法。为了拯救自己赶紧想办法吧。 输入 输入包含多组每组格式如下。 第一行包含两个整数n,m分别代表n个隘口这些隘口之间有m个通道。 下面m行每行包含两个整数ab表示从a出发有一条通道到达b隘口注意通道是单向的。 输出 如果天灾军团可以不修建任何通道就到达1号隘口那么输出最少经过多少通道否则输出NO。 示例输入 2 1
1 2
2 1
2 1 示例输出 NO
1提示 #include stdio.h #include stdlib.h #includequeue #define MAX 100 using namespace std; typedef struct arcnode { int adj; } arcnode, adjmatrix[1000][1000]; typedef struct { adjmatrix a; int vn; int an; } MG; struct node { int data;//记录顶点 int step;//记录走过最少的通道数 }t, s; int k;//初始点 int i, j; int create(MG g, int n, int m)//邻接矩阵的生成 { int v1, v2; g.vn n; g.an m; for(i1; ig.vn; i) for(j1; jg.vn; j) g.a[i][j].adj 0; for(i1; ig.an; i) { scanf(%d %d, v1, v2); if(v1 ! v2) g.a[v1][v2].adj 1; } return 1; } int v[1000];//标记数组 void bfs(MG g) { queuenode q;//结构体进队 for(i0; ig.vn; i) v[i] 0;//初始化 t.data g.vn; t.step 0; v[t.data] 1;//从最后一个结点开始遍历 q.push(t); while(!q.empty()) { s q.front(); q.pop(); if(s.data 1)//走到目的地 { printf(%d\n,s.step); return; } for(j1; jg.vn; j) { if(g.a[s.data][j].adj 1 !v[j]) { v[j] 1; t.data j; t.step s.step1; q.push(t); } } } printf(NO\n); } int main() { MG g; int n, m; while(~scanf(%d %d, n, m)) { create(g, n, m); bfs(g); } return 0; }
