青岛金融网站建设,广州建设工程交易中心电话,电子商务网站有哪些功能,网站建设销售员工作内容题目描述 在有向图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 。 输入输出样例 输入样例#13 2
1 2
2 1
1 3 输出样例#1-1 输入样例#26 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5 输出样例#23 说明 解释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。 这道题我们可以用逆向思维来想 如果一个点能到达终点那么终点也一定能到达这个点 这样就简单了 从终点跑一遍BFS算出每一个点的访问次数 然后把不能走的点删去 最后spfa带走 一个很有意思的能够找出访问次数而且不会死循环的方法 1 int toedge[i].v; 2 if(cs[to])continue; 3 q.push(to); 完整代码 1 #includeiostream2 #includecstdio3 #includecstring4 #includecmath5 #includequeue6 #define INF 0x7ffffff7 using namespace std;8 int read(int n)9 {10 int flag0,x0;char c/;11 while(c0||c9){cgetchar();if(c-)flag1;}12 while(c0c9)xx*10(c-48),cgetchar();13 if(flag)n-x;else nx;14 }15 const int MAXN200001;16 int n,m,bgx,bgy;17 int rudu[MAXN];18 struct node19 {20 int u,v,w,nxt;21 }edge[MAXN];22 int num1;23 int head[MAXN];24 int flag[MAXN];// 记录每个值是否能够到达终点 25 int cs[MAXN];26 int dis[MAXN];27 int vis[MAXN];28 void add_edge(int ll,int rr,int ww)29 {30 edge[num].ull;31 edge[num].vrr;32 edge[num].www;33 edge[num].nxthead[ll];34 head[ll]num;35 }36 void bfs()37 {38 queueintq;39 int tot0;40 q.push(bgx),tot;41 while(q.size()!0)42 {43 int pq.front();44 q.pop();45 for(int ihead[p];i!-1;iedge[i].nxt)46 {47 int toedge[i].v;48 if(cs[to])continue;49 q.push(to);50 }51 }52 //rudu[bgy]0;53 for(int i1;in;i)54 if(rudu[i]!cs[i]i!bgy)55 flag[i]1;56 }57 void dele()58 {59 for(int i1;inum;i)60 {61 if(flag[edge[i].u]!0)62 {63 edge[i].u-1;64 edge[i].v-1;65 edge[i].w-1;66 edge[i].nxt-1;67 }68 }69 }70 void spfa()71 {72 queueintq;73 q.push(bgx);74 dis[bgx]0;75 while(q.size()!0)76 {77 int pq.front();78 q.pop();79 vis[p]0;80 for(int ihead[p];i!-1;iedge[i].nxt)81 {82 if(edge[i].u-1)continue;83 int toedge[i].v;84 if(dis[to]dis[p]edge[i].w)85 {86 dis[to]dis[p]edge[i].w;87 if(vis[to]0)88 {89 vis[to]1;90 q.push(to);91 }92 }93 }94 }95 if(dis[bgy]INF)96 printf(-1);97 else98 printf(%d,dis[bgy]);99 }
100 int main()
101 {
102 freopen(roadb.in,r,stdin);
103 freopen(roadb.out,w,stdout);
104 read(n);read(m);
105 for(int i1;in;i)head[i]-1,dis[i]INF;
106 for(int i1;im;i)
107 {
108 int x,y;
109 read(x);read(y);
110 add_edge(y,x,1);
111 rudu[x];
112 }
113 read(bgy);read(bgx);
114 bfs();
115 dele();
116 spfa();
117 return 0;
118 } 转载于:https://www.cnblogs.com/zwfymqz/p/6899931.html
