品牌学习网站,手机网站制作公司报价单,微站小程序,wordpress源码整合题目描述 在有向图G 中#xff0c;每条边的长度均为1 #xff0c;现给定起点和终点#xff0c;请你在图中找一条从起点到终点的路径#xff0c;该路径满足以下条件#xff1a; 1 #xff0e;路径上的所有点的出边所指向的点都直接或间接与终点连通。 2 #xff0e;在满足…题目描述 在有向图G 中每条边的长度均为1 现给定起点和终点请你在图中找一条从起点到终点的路径该路径满足以下条件 1 路径上的所有点的出边所指向的点都直接或间接与终点连通。 2 在满足条件1 的情况下使路径最短。 注意图G 中可能存在重边和自环题目保证终点没有出边。 请你输出符合条件的路径的长度。 输入输出格式 输入格式 输入文件名为road .in。 第一行有两个用一个空格隔开的整数n 和m 表示图有n 个点和m 条边。 接下来的m 行每行2 个整数x 、y 之间用一个空格隔开表示有一条边从点x 指向点y 。 最后一行有两个用一个空格隔开的整数s 、t 表示起点为s 终点为t 。 输出格式 输出文件名为road .out 。 输出只有一行包含一个整数表示满足题目᧿述的最短路径的长度。如果这样的路径不存在输出- 1 。 输入输出样例 输入样例#1 3 2
1 2
2 1
1 3 输出样例#1 -1 输入样例#2 6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5 输出样例#2 3 说明 解释1 如上图所示箭头表示有向道路圆点表示城市。起点1 与终点3 不连通所以满足题目᧿述的路径不存在故输出- 1 。 解释2如上图所示满足条件的路径为1 - 3- 4- 5。注意点2 不能在答案路径中因为点2连了一条边到点6 而点6 不与终点5 连通。对于30%的数据0n≤100m≤20对于60%的数据0n≤1000m≤2000对于100%的数据0n≤10,0000m≤200,0000xyst≤nx≠t。 解题思路 利用宽搜先去掉所有的不能使用的点具体就是把能跑到的赋值在用循环找到跑不到的把与他相连的点都去掉只需要去掉直接相连的就行然后跑一边dij或者spfa就能过这里要注意的是点和边都有点多应该用链表储存 program ChoosePath;
var pd:Array[0..10000] of boolean;u,v,head,next:array[0..200000] of longint;b,d,c:array[0..10000] of longint;i,j,m,n,now,x,y,h,t,l,sum:Longint;
procedure dij;
var i,min,minn,l:longint;
beginfor i:1 to n do d[i]:maxlongint;d[y]:0;for i:1 to n dobeginmin:maxlongint;for j:1 to n do if (mind[j]) and ( pd[j]) thenbeginmin:d[j];minn:j;end;if minmaxlongint then exit;pd[minn]:false;l:head[minn];while l0 dobeginif (min1d[v[l]]) and ( pd[v[l]]) then d[v[l]]:min1;l:next[l];end;end;
end;beginread(n,m);for i:1 to m dobeginread(v[i],u[i]);next[i]:head[u[i]];head[u[i]]:i;end;read(x,y);h:0;t:0;inc(t);b[t]:y;while ht dobegininc(h);now:b[h];pd[now]:true;l:head[now];while l0 dobeginif pd[v[l]]false thenbegininc(t);b[t]:v[l];pd[v[l]]:true;end;l:next[l]end;end;for i:1 to n do if pd[i]false thenbegininc(sum);c[sum]:i;end;for i:1 to sum dobeginl:head[c[i]];while l0 dobeginpd[v[l]]:false;l:next[l];end;end;dij;writeln(d[x]);
end. 转载于:https://www.cnblogs.com/wuminyan/p/4746300.html
