修LATEX
查看原帖
修LATEX
906452
MARSandEARTH楼主2023/12/13 09:09

题意描述:

给你一张无向图,一共有 nn 个点 (2≤n≤103)(2\le n\le10^3),由 mm 条边连接起来 (1≤m≤104)(1\le m\le10^4),现在要在任意一对没有连边的点之间连上一条边,并且保证 ss 到 tt 之间的最短路径长度不变(最短路径长度表示 ss 到 tt 最少经过的边的数量)(1≤s,t≤n,s≠t)(1\le s,t\le n,s\neq t),请你求出一共有多少条这样的边。

输入格式:

第一行输入四个整数 n,m,s,tn,m,s,t。

接下来的 mm 行每行有两个整数 ui,vi (1≤ui,vi≤n,ui≠vi)u_i,v_i\ (1\le u_i,v_i\le n,u_i\neq v_i),表示 ui,viu_i,v_i 之间有一条无向边。

输出格式:

共 11 行,表示合法的加边方案数。

2023/12/13 09:09
加载中...