B27 A*算法第K短路[POJ2449]Remmarguts' Date

ID: 1093

传统题

1000ms

64MiB

难度: 7

上传者:

标签>

入门

Description

0x20搜索（0x27A*）例题1：第K短路【POJ2449】 Remmarguts' Date ## 【题意】给定一张 $N$ 个点（编号$1,2…N$），$M$ 条边的有向图，求从起点 $S$ 到终点 $T$ 的第 $K$ 短路的长度，路径允许重复经过点或边。

第一行两个整数 $N$ 和 $M$ 。

下来 $M$ 行，每行包含三个整数 $A$ , $B$ 和 $L$ ，表示点 $A$ 与点 $B$ 之间存在有向边，且边长为 $L$ 。

最后一行包含三个整数 $S$ , $T$ 和 $K$ ，分别表示起点 $S$ ，终点 $T$ 和第 $K$ 短路。

$1≤S,T≤N≤1000,0≤M≤10^5,1≤K≤1000,1≤L≤100$

输出占一行，包含一个整数，表示第K短路的长度，如果第K短路不存在，则输出-1。