2023年7月30日发(作者：)

历年NOIP真题题⽬描述在有向图 (G) 中，每条边的长度均为 (1)，现给定起点和终点，请你在图中找⼀条从起点到终点的路径，该路径满⾜以下条件：路径上的所有点的出边所指向的点都直接或间接与终点连通。在满⾜条件(1)的情况下使路径最短。注意：图 (G) 中可能存在重边和⾃环，题⽬保证终点没有出边。请你输出符合条件的路径的长度输⼊格式第⼀⾏有两个⽤⼀个空格隔开的整数 (n) 和 (m)，表⽰图有 (n) 个点和 (m) 条边。接下来的 (m) ⾏每⾏ (2) 个整数 (x,y)，之间⽤⼀个空格隔开，表⽰有⼀条边从点 (x) 指向点(y)。最后⼀⾏有两个⽤⼀个空格隔开的整数 (s, t)，表⽰起点为 (s)，终点为 (t)。输出格式输出只有⼀⾏，包含⼀个整数，表⽰满⾜题⽬描述的最短路径的长度。如果这样的路径不存在，输出(-1)输⼊13 21 22 11 3输出1-1输⼊26 61 21 32 62 5

4 53 41 5输出23分析题⽬要求所有点的出边所指向的点都直接与间接与终点联通。⾸先我的思路是⽤⼀个并查集将与终点有连接的点记录起来，但是有重边和⾃环，没办法⽤并查集。我们采取SPFA建反图跑⼀边最短路，以终点为起点，将每个点到终点的最短路记录下来，如果不能到达，那么在BFS中就不加⼊。代码#include #include #include #include #include using namespace std;typedef long long ll;const int N = 6e6;int n,m,u,v,s,t;struct edge{ int from; int to; int dis; int next;}e[N],E[N];int head[N],cnt;void add(int u,int v){ ++cnt; e[cnt].from = u; e[cnt].to = v; e[cnt].next = head[u]; head[u] = cnt;}int HEAD[N],tot;void add2(int u,int v,int w){ ++tot; E[tot].from = u; E[tot].to = v; E[tot].dis = w; E[tot].next = HEAD[u]; HEAD[u] = tot;}int mapp[N];bool vis[N];queue q;void SPFA(int u){ memset(mapp,0x3f,sizeof(mapp)); memset(vis,0,sizeof(vis)); mapp[u] = 0; vis[u] = true; (u); while(!()) { int x = (); vis[x] = false; (); for(int i=HEAD[x];i;i=E[i].next) { int y = E[i].to; if(mapp[y] > mapp[x] + E[i].dis) { mapp[y] = mapp[x] + E[i].dis; if(vis[y] == false) { vis[y] = true; (y); } } } }}int dis[N];bool check(int x){ for(int i=head[x];i;i=e[i].next) { int y = e[i].to; if(mapp[y] == 1061109567) return false; } return true;}void bfs(){

memset(vis,0,sizeof(vis)); queue q; (s); memset(dis,0x3f,sizeof(dis)); dis[s] = 0; vis[s] = true; while(!()) { int x = (); (); for(int i=head[x];i;i=e[i].next) { int y = e[i].to; if(vis[y] == true) continue; if(mapp[y] == 1061109567 || check(y) == false) continue; //如果它所连的边也不能到达终点，那么也将它排除。 int w = 1; if(dis[y] > dis[x] + w)

dis[y] = dis[x] + w; if(vis[y] == false) (y); vis[y] = true; } }}int main(){ cin>>n>>m; for(int i=1;i<=m;i++) { cin>>u>>v; add(u,v); add2(v,u,1); } cin>>s>>t; SPFA(t); bfs(); if(dis[t] == 1061109567) puts("-1"); else cout<#include #include #include #include #define lll __int128using namespace std;const int N=2e7;lll gcd(lll a,lll b){ if(b == 0) return a; return gcd(b,a%b);}struct edge{ int from; int to; int dis; int next;}e[N];int head[N],cnt;void add(int u,int v){ ++cnt; e[cnt].from = u; e[cnt].to = v; e[cnt].next = head[u]; head[u] = cnt;}struct node{ lll son; lll mom; node() { lll son = 0; lll mom = 0; }}ans[N];node check(node a,node b){ node sum; if( == 0 && == 0) { = ; = ; return sum; } lll p = /gcd(,)*; = p; = (p/*)+(p/*); lll t = gcd(,); /= t; /= t; return sum;}int n,m;int x;int num[N];int ru[N],chu[N];queue q;void print(lll n) { if(n > 9) print(n / 10); putchar(n % 10 + 48); //n % 10+'0'(48)表⽰字符0~9

//putchar输出的是字符。}int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { cin>>num[i]; for(int j=1;j<=num[i];j++) { cin>>x; add(i,x); ru[x]++; chu[i]++;

} } for(int i=1;i<=n;i++) if(ru[i] == 0) { (i); ans[i].son = 1; ans[i].mom = 1; } while(!()) { int x = (); if(num[x] != 0) ans[x].mom *= num[x]; (); for(int i=head[x];i;i=e[i].next) { int y = e[i].to; ans[y] = check(ans[y],ans[x]); ru[y]--; if(ru[y] == 0) (y); //cout<

} return 0;}