培训的网站建设,网站建设嘉兴,xammp wordpress,阳江房产信息网官网最短路计数
题目描述
给出一个 NNN 个顶点 MMM 条边的无向无权图#xff0c;顶点编号为 1∼N1\sim N1∼N。问从顶点 111 开始#xff0c;到其他每个点的最短路有几条。
输入格式
第一行包含 222 个正整数 N,MN,MN,M#xff0c;为图的顶点数与边数。
接下来 MMM 行…最短路计数
题目描述
给出一个 NNN 个顶点 MMM 条边的无向无权图顶点编号为 1∼N1\sim N1∼N。问从顶点 111 开始到其他每个点的最短路有几条。
输入格式
第一行包含 222 个正整数 N,MN,MN,M为图的顶点数与边数。
接下来 MMM 行每行 222 个正整数 x,yx,yx,y表示有一条由顶点 xxx 连向顶点 yyy 的边请注意可能有自环与重边。
输出格式
共 NNN 行每行一个非负整数第 iii 行输出从顶点 111 到顶点 iii 有多少条不同的最短路由于答案有可能会很大你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 iii 则输出 000。
样例
样例输入
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5样例输出
1
1
1
2
4提示
111 到 555 的最短路有 444 条分别为 222 条 1→2→4→51\to 2\to 4\to 51→2→4→5 和 222 条 1→3→4→51\to 3\to 4\to 51→3→4→5由于 4→54\to 54→5 的边有 222 条。
对于 20%20\%20% 的数据1≤N≤1001\le N \le 1001≤N≤100对于 60%60\%60% 的数据1≤N≤1031\le N \le 10^31≤N≤103对于 100%100\%100% 的数据1≤N≤1061\le N\le10^61≤N≤1061≤M≤2×1061\le M\le 2\times 10^61≤M≤2×106。
思路
无向无权图。可使用bfs遍历因为路径的权重都为1。 当前图中存在自环但自环并不影响bfs遍历的最短路。 然后就是重边会对结果造成影响需要我们考虑。
代码实现
import java.util.*;public class Main{static int MOD (int)1e5 3;public static void main(String[] args){Scanner sc new Scanner(System.in);int n sc.nextInt(), len sc.nextInt();ListInteger list[] new ArrayList[n1];// 去环已经进入过队列的结点将不再进入队列boolean[] vis new boolean[n1];int[] depth new int[n1];// 结果。int[] ans new int[n1];for(int i 1; i n; i) list[i] new ArrayList();int x, y;for (int i 0; i len; i) {x sc.nextInt();y sc.nextInt();list[x].add(y);list[y].add(x);}QueueInteger queue new ArrayDeque();depth[1] 0;vis[1] true;ans[1] 1;queue.offer(1);while(!queue.isEmpty()){int cur queue.poll();for(int next : list[cur]){if(!vis[next]){vis[next] true;depth[next] depth[cur] 1;queue.offer(next);}// next结点只有深度为 depth[next]的时候才会更新。// 换句话说就是只有第一次与第一次相同时间到达next时才会更新值。if(depth[next] depth[cur] 1) ans[next] (ans[next] ans[cur]) % MOD;}}for(int i 1; i n; i) System.out.println(ans[i]);sc.close();}
}中位数
题目描述
给出 1,2,...,n1,2,...,n1,2,...,n 的一个排列统计该排列有多少个长度为奇数的连续子序列的中位数是 bbb。中位数是指把所有元素从小到大排列后位于中间的数。
输入格式
第一行为两个正整数 nnn 和 bbb第二行为 1,2,...,n1,2,...,n1,2,...,n 的排列。
输出格式
输出一个整数即中位数为 bbb 的连续子序列个数。
样例
样例输入
7 4
5 7 2 4 3 1 6样例输出
4提示
数据规模与约定 对于 30%30\%30% 的数据中满足 n≤100n \le 100n≤100 对于 60%60\%60% 的数据中满足 n≤1000n \le 1000n≤1000 对于 100%100\%100% 的数据中满足 n≤100000,1≤b≤nn \le 100000,1 \le b \le nn≤100000,1≤b≤n。
思路
因为满足需要的区间一定包含b, 所以我们可以先把b在数组中的位置找到。再到基础上拓展区间。 需要b成为区间的中位数即是需要区间内大于b的数的数量等于区间内小于b的数的数量我们可以把大于b的数记作1 小于b的数记为-1。然后只需要左边区间加右边区间 0即为找到一个区间。还需要特别注意区间长度为奇数也是条件之一
代码实现
import java.util.*;public class Main{public static void main(String[] args){Scanner sc new Scanner(System.in);int n sc.nextInt(), b sc.nextInt();int[] arr new int[n1];for(int i 1; i n; i) arr[i] sc.nextInt();int index query(arr, b);HashMapInteger, Integer one new HashMap();HashMapInteger, Integer two new HashMap();two.put(0, 1);int val 0;for(int i index - 1; i 0; i--){val (arr[i] b ? 1 : -1);if((index - i) % 2 1) one.put(val, one.getOrDefault(val, 0) 1);else two.put(val, two.getOrDefault(val, 0) 1);}val 0;long ans 0;for(int i index; i n; i){val (arr[i] b ? 0 : (arr[i] b ? 1 : -1));if((i-index) % 2 1) ans one.getOrDefault(-val, 0);else ans two.getOrDefault(-val, 0);}System.out.println(ans);sc.close();}static int query(int[] arr, int b){for(int i 1; i arr.length; i){if(arr[i] b) return i; }return -1;}
}
