ABC319 G - Counting Shortest Paths

2024-04-03 09:28
文章标签 counting shortest paths abc319

本文主要是介绍ABC319 G - Counting Shortest Paths,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

解题思路

  • 按照到1的距离远近,进行分层
  • 1为第一层
  • 分层步骤:用一个集合记录还未定层的点,用bfs逐层确定
  • 对于当前点x
  • 与其有连边的(不是删边)且还未确定的点,确定为x的下一层,入队列
  • 没连边且还未确定的点,入集合(每次决策建立新集合,用浅拷贝)
  • 直到集合为空
  • 此时,到n的最优距离确定
  • 长度为dis[n]的方案数即为答案
  • 统计方案数,考虑容斥
  • 逐层统计
  • 对于当前层,不考虑删边,到该层每一个点的最优距离的方案数(dis+1)为上一层的方案数
  • 考虑删边,若u\rightarrow v删去,则u的方案不会被统计到v中(不是最优,+1),f[v]=(f[v]-f[x]+md)
  • 注意无法到达的点距离为0,需处理
  • 最终答案为f[n]
  • 对于每层的点不会有重复,使用Set<Integer>[] dep=new HashSet[n+1];
  • Treeset(稍慢,因为有排序)
  • 防止超时(Vector太慢)

import java.io.*;
import java.math.BigInteger;
import java.util.*;//implements Runnable
public class Main {static long md=(long)998244353;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;static int N=200010;static int n=0;static int m=0;static void solve() throws Exception{AReader input=new AReader();
//        String fileName="C:\\Users\\Lenovo\\Downloads\\055.txt";
//		Scanner input=new Scanner(new FileReader(fileName));//        BufferedReader input = new BufferedReader(new FileReader(fileName));PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));String al="abcdefghijklmnopqrstuvwxyz";char[] ac=al.toCharArray();n=input.nextInt();m=input.nextInt();Set<Integer>[] e=new Set[N+1];for(int i=1;i<=n;++i)e[i]=new HashSet<>();HashSet<Integer> hs=new HashSet<>();for(int i=2;i<=n;++i)hs.add(i);for(int i=1;i<=m;++i){int u=input.nextInt();int v=input.nextInt();e[u].add(v);e[v].add(u);}int[] dis=new int[N+1];Queue<Integer> q=new LinkedList<>();q.add(1);dis[1]=1;while(!q.isEmpty()){HashSet<Integer> now=new HashSet<>();int x=q.poll();for(int v:hs){if(!e[x].contains(v)){dis[v]=dis[x]+1;q.add(v);}else{now.add(v);}}hs=now;}if(dis[n]==0){out.println("-1");}else{Set<Integer>[] dep=new HashSet[n+1];for(int i=0;i<=n;++i)dep[i]=new HashSet<>();for(int i=1;i<=n;++i){dep[dis[i]].add(i);}long[] f=new long[N+1];long sum=1;f[1]=1;for(int i=2;i<=dis[n];++i){for(int x:dep[i]){f[x]=sum;}for(int x:dep[i-1]){for(int v:e[x]){if(dep[i].contains(v)){f[v]=(f[v]+md-f[x])%md;}}}sum=0;for(int x:dep[i]){sum=(sum+f[x])%md;}}out.println(f[n]);}out.flush();out.close();}public static void main(String[] args) throws Exception{solve();}//	public static final void main(String[] args) throws Exception {
//		  new Thread(null, new Tx2(), "线程名字", 1 << 27).start();
//	}
//		@Override
//		public void run() {
//			try {
//				//原本main函数的内容
//				solve();
//
//			} catch (Exception e) {
//			}
//		}staticclass AReader{BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bf=new BufferedReader(new InputStreamReader(System.in));st=new StringTokenizer("");bw=new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException{//确定下一个token只有一个字符的时候再用return next().charAt(0);}public int nextInt() throws IOException{return Integer.parseInt(next());}public long nextLong() throws IOException{return Long.parseLong(next());}public double nextDouble() throws IOException{return Double.parseDouble(next());}public float nextFloat() throws IOException{return Float.parseFloat(next());}public byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}public void println() throws IOException {bw.newLine();}public void println(int[] arr) throws IOException{for (int value : arr) {bw.write(value + " ");}println();}public void println(int l, int r, int[] arr) throws IOException{for (int i = l; i <= r; i ++) {bw.write(arr[i] + " ");}println();}public void println(int a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(int a) throws IOException{bw.write(String.valueOf(a));}public void println(String a) throws IOException{bw.write(a);bw.newLine();}public void print(String a) throws IOException{bw.write(a);}public void println(long a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(long a) throws IOException{bw.write(String.valueOf(a));}public void println(double a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(double a) throws IOException{bw.write(String.valueOf(a));}public void print(char a) throws IOException{bw.write(String.valueOf(a));}public void println(char a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}}
}

这篇关于ABC319 G - Counting Shortest Paths的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/872534

相关文章

POJ 2386 Lake Counting(DFS)

题目: http://poj.org/problem?id=2386 题解: 遍历一次,遇到w,一次DFS后,与此w连接的所有w都被替换成‘ . ’,直到遍历完图中不再存在w为止,总共进行DFS的次数就是答案了。 代码: #include<stdio.h>int N,M;char map[110][110];void dfs(int x,int y){map[x][y]='

POJ 2001 Shortest Prefixes(字典树入门)

题目: http://poj.org/problem?id=2001 题意: 找到多个字符串中,各自唯一的最短子串,例如 carte 与 carce 各自唯一的最短子串为cart与carc,即不会与其它字符串的子串重复。 思路: 字典树 解题心得: 更新关键值的时机很重要 代码: #include<stdio.h>#include<string>typedef str

大数据Java基础-JAVA IO 9】java IO流 (九) Path、Paths、Files的使用

1.NIO的使用说明: >Java NIO (New IO,Non-Blocking IO)是从Java 1.4版本开始引入的一套新的IO API,可以替代标准的Java IO AP。 >NIO与原来的IO同样的作用和目的,但是使用的方式完全不同,NIO支持面向缓冲区的(IO是面向流的)、基于通道的IO操作。 >NIO将以更加高效的方式进行文件的读写操作。 >随着 JDK 7 的发布,Java对N

最短路径(Shortest Path)

单源最短路径问题 Dijkstra算法:基于递推的思想设计 未达顶点的最短路径一定是由已到达顶点的最短路径求出 所有顶点之间的最短路径,任意两个顶点之间的最短路径 Floyd算法:只是Dijkstra最短路径算法的加强,其本质还是递推

[LeetCode] 338. Counting Bits

题:https://leetcode.com/problems/counting-bits/description/ 题目 Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary repres

《Zero-Shot Object Counting》CVPR2023

摘要 论文提出了一种新的计数设置,称为零样本对象计数(Zero-Shot Object Counting, ZSC),旨在测试时对任意类别的对象实例进行计数,而只需在测试时提供类别名称。现有的类无关计数方法需要人类标注的示例作为输入,这在许多实际应用中是不切实际的。ZSC方法不依赖于人类标注者,可以自动操作。研究者们提出了一种方法,可以从类别名称开始,准确识别出最佳的图像块(patches),用

【HDU】2807 The Shortest Path 最短路

传送门:【HDU】2807 The Shortest Path 题目分析:题目很简单,矩阵计算出两个城市的连通性,建边,然后每次询问求最短路回答(或者floyd预处理)。 当然暴力的代价是惨痛的,用堆优化+dij+输入优化最多800ms。 然后很好奇前面的是怎么跑的这么快的,看了别人写的题解才发现,原来他们是用了hash的方法将二维化为一维了,虽然可能会错误,但在出题人不是故意去卡的情

【HDU】1595 find the longest of the shortest 枚举+最短路

传送门:【HDU】1595 find the longest of the shortest 题目分析:首先求出一条最短路,记录下最短路上用到的边,枚举删除每一条边,求一次最短路,求完后恢复删除的边。重复这一过程直到枚举完所有的边为止。所有删除边后求得的最短路里最长的那条就是答案。 代码如下: #include <cstdio>#include <cstring>

【HDU】4871 Shortest-path tree 最短路+点分治

传送门:【HDU】4871 Shortest-path tree 题目分析: 学了点分治后来看这道题,简直就是水题。。。 但是我竟然花了将近一个晚上才写出来。。。就因为一个地方写漏了T U T。。 首先根据题意求一棵树,最短路一下,然后最小字典序就按照编号顺序遍历邻接表给节点标记。 剩下的就是树分治的事了。 在以重心X为根的子树中,按照X的子节点v的子树中最长路径包含节点数升序遍

LeetCode 63 Unique Paths II

题意: 给出一个带有障碍物的棋盘,每次行动向下或向右移动一格,求从左上角到右下角有几种方案。 思路: 简单dp题,假设dp[i][j]表示第i行第j列的方案数,那么状态转移方程就为 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 。 注意下边界条件就好了,而且对于障碍物,直接把dp清零即可。 可以发现这个dp只和当前行和上一行有关,进而做空间优化,用一