搜索网站入口,旅游产业网站app建设的市场分析,dz论坛可以做招聘网站,做网站购买虚拟主机送模板吗题目描述 在有向图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。 正反存边 反跑dfs标记终点能到达的点 也就是能到达终点的点 然后把出边不能到达终点的点标记为不能走 然后正跑spfa 屠龙宝刀点击就送 #include vector
#include cstdio
#include queue
#define N 10005
using namespace std;
vectorintG1[N],G2[N];
bool cant[N],vis[N];
int n,m,s,t,dis[N];
void dfs(int x)
{vis[x]1;for(int i0;iG2[x].size();i){int vG2[x][i];if(!vis[v]) dfs(v);}
}
int main()
{scanf(%d%d,n,m);for(int x,y,i1;im;i){scanf(%d%d,x,y);G1[x].push_back(y);G2[y].push_back(x); }scanf(%d%d,s,t);dfs(t);for(int i1;in;i){bool flagfalse;if(!vis[i]) {cant[i]1;continue;}for(int j0;jG1[i].size();j){int vG1[i][j];if(!vis[v]) {flag1;break;} }if(flag) {cant[i]1;continue;}}for(int i1;in;i) dis[i]0x3f3f3f3f,vis[i]0;dis[s]0;vis[s]1;queueintq;q.push(s);for(int now;!q.empty();){nowq.front();q.pop();vis[now]0;if(cant[now]) continue;for(int i0;iG1[now].size();i){int vG1[now][i];if(dis[v]dis[now]1){dis[v]dis[now]1;if(!vis[v]){q.push(v);vis[v]1; }}}}dis[t]0x3f3f3f3f?printf(-1):printf(%d,dis[t]);return 0;
} 转载于:https://www.cnblogs.com/ruojisun/p/7506696.html
