| 题目名称 | 3490. [POJ 2449]第K短路 |
|---|---|
| 输入输出 | remmarguts.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 5 |
| 题目来源 |
 gao
于2020-10-23加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：9， 提交：26， 通过率：34.62% | ||||
 Oasiz |
100 | 0.008 s | 3.91 MiB | C++ |
 liuyiche |
100 | 0.011 s | 1.85 MiB | C++ |
|
liuyiche |
100 | 0.012 s | 1.85 MiB | C++ |
|
yrtiop |
100 | 0.013 s | 1.44 MiB | C++ |
|
锝镆氪锂铽 |
100 | 0.014 s | 2.04 MiB | C++ |
 Eddy2008 |
100 | 0.066 s | 1.25 MiB | C++ |
 增强型图元文件 |
100 | 0.196 s | 3.03 MiB | C++ |
|
Eddy2008 |
100 | 0.882 s | 1.29 MiB | C++ |
 tat |
100 | 0.910 s | 2.79 MiB | C++ |
|
liuyiche |
80 | 0.011 s | 1.85 MiB | C++ |
| 关于 第K短路 的近10条评论(全部评论) |
|---|
【题目描述】
给定一张$n$个点，$m$条有向边，求从起点$s$到终点$t$的第$k$短路的长度，路径允许重复经过点或边。其中$1\le s,t \le n \le 1000,0 \le m \le 10^5,1 \le k\le 1000$。
【输入格式】
第一行包含两个整数$n$和$m$。
以下$m$行每行包含三个整数$x, y, z(1\le x,y \le n, 1\leq z\leq 100)$，表示一条权值为$z$的有向边$<x,y>$。
最后一行由三个整数$s,t,k$组成。
【输出格式】
输出一行：第K最短路。
如果不存在，则应输出“-1”。
【样例输入】
2 2 1 2 5 2 1 4 1 2 2
【样例输出】
14
【来源】
《算法竞赛进阶指南》POJ2449