#P17199. PM8791第K短路

    ID: 16358 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-强连通分量Floyd–Warshall双射计数二分第 k 小类欧几里得算法完全背包

PM8791第K短路

题目描述

给定一个带正权的有向图,它满足以下两个条件:

  • 每个顶点至多属于一个简单环;
  • 对任意两个顶点 u,vu,v,从 uu 到 vv 至多存在一条简单路径。

图由一个 n×nn\times n 的数字字符矩阵描述。第 ii 行第 jj 个字符为 0,表示不存在从 ii 到 jj 的边;否则该字符是 1 到 9,表示从 ii 到 jj 的有向边的权值。

给定起点 ss、终点 tt 和正整数 kk,求从 ss 到 tt 的第 kk 短游走的长度。游走可以重复经过顶点和边,因此可以反复绕行图中的环。

如果多条不同游走的长度相同,它们仍要分别计数。如果从 ss 到 tt 的游走不足 kk 条,输出 −1-1。

输入格式

第一行包含四个整数 n,k,s,tn,k,s,t,分别表示顶点数、所求排名、起点和终点。

接下来 nn 行,每行包含一个长度为 nn 的数字字符串,描述图的邻接矩阵。

顶点编号为 00 到 n−1n-1。

输出格式

输出一个整数,表示从 ss 到 tt 的第 kk 短游走的长度;如果这样的游走不存在,输出 −1-1。

样例 1

4 1 0 2
0100
0020
0003
4000
3

样例 2

4 2 0 2
0100
0020
0003
4000
13

样例 3

3 1 1 2
011
000
000
-1

样例 4

6 3 0 3
010000
001010
000101
000000
010000
001000
5

数据范围与保证

  • 2≤n≤502\le n\le50;
  • 1≤k≤10121\le k\le10^{12};
  • 0≤s,t<n0\le s,t<n 且 s≠ts\ne t;
  • 邻接矩阵中的字符均为 0 到 9;
  • 矩阵主对角线上的字符均为 0;
  • 图满足题目描述中的两项结构限制。

术语说明

  • 简单路径是一个顶点互不相同的有序序列,序列中每个顶点都有一条边指向下一个顶点;
  • 简单环首尾顶点相同,除首尾外的其余顶点互不相同,并且序列中每个顶点都有一条边指向下一个顶点。

说明

样例 1 中的最短游走为 0→1→20\to1\to2,长度为 33。

样例 2 中可以沿环 0→1→2→3→00\to1\to2\to3\to0 绕行一次,再到达顶点 22,得到长度为 1313 的第二短游走。

样例 4 中最短游走长度为 33,随后两条不同游走的长度都为 55,因此第三短游走的长度为 55。