英铭科技做网站和设计制作更专业,公众平台推广,石家庄哪里有做网站,世界500强企业市值排名题目
一个有向图#xff0c;要求满足要求的最短路径#xff0c;要求为#xff1a; 路径上的所有点的出边所指向的点都直接或间接与终点连通。 输入1
3 2 (3个点,2条边) 1 2 (1和2之间可以连接) 2 1 1 3 (从1到3)
输出1
-1
输入2
6 6 1 2 1 3 2 6 2 5 4 5 3…题目
一个有向图要求满足要求的最短路径要求为 路径上的所有点的出边所指向的点都直接或间接与终点连通。 输入1
3 2 (3个点,2条边) 1 2 (1和2之间可以连接) 2 1 1 3 (从1到3)
输出1
-1
输入2
6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5
输出2
3 解题思路
其实我们就求出满足要求的点然后在这些点里找最短路还有本人这里的方法比较复杂和麻烦 代码
#includecstdio
using namespace std;
struct woc{int next,x,y;
};//日常邻接表
woc a[200001],lt[200001];
int xx,yy,n,m,k,state[10001],ls[10001],t,head,tail,f[10001],star,over;
int fls[10001];
bool ltfl[10001];
bool v[10001];
void check()//求所有可以直接或间接到终点的边
{int t0;int head0;int tail1;state[1]over;ltfl[state[1]]true;//初始化while (head!tail){head;head(head-1)%n1;tfls[state[head]];//求边while (t!0){if (!ltfl[lt[t].y]){tail;tail(tail-1)%n1;state[tail]lt[t].y;ltfl[lt[t].y]true;//标记}tlt[t].next;//求下一条边}}
}
bool ok(int x)//是否满足要求
{int tls[x];while (t!0){if (!ltfl[a[t].y]) return false;ta[t].next;}return true;
}
int main()
{scanf(%d%d,n,m);state[1]1;int u0; for (int i1;im;i){scanf(%d,xx);scanf(%d,yy);a[u].nextls[xx];ls[xx]u;a[u].xxx;a[u].yyy;//边lt[u].nextfls[yy];fls[yy]u;lt[u].yxx;lt[u].xyy;//记录一条回去的边} scanf(%d%d,star,over);for (int i1;in;i) f[i]2147483647;//初始化 check();//求所有可以直接或间接到终点的边head0;tail1;state[1]star;v[state[1]]true;f[star]0;//初始化×2while (head!tail){head;//出队head(head-1)%n1;//循环队列tls[state[head]];while (t!0){if (f[a[t].x]1f[a[t].y] ok(a[t].y))//判断是否满足要求{f[a[t].y]f[a[t].x]1;//松弛if (!v[a[t].y]){tail;//入队tail(tail-1)%n1;//循环队列state[tail]a[t].y;v[a[t].y]true;}}ta[t].next;//下一条边}v[state[head]]false;//解封}if (f[over]2147483647) printf(-1);//是否有解else printf(%d\n,f[over]);
}
