#106. 单源最短路径

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: StudyingFather

题目描述

数据暂缺,欢迎各位提供卡SPFA及其优化算法的数据。

给一个 n 个点和 m 条边的有向图,求从 s t 的最短路。

输入格式

第一行包含四个整数, n,m,s,t

接下来 m 行,每行三个整数, u_i,v_i,w_i ,表示有一条从 u_i v_i ,边权为 w_i 的边。

图中保证没有任何重边和自环,且保证存在一条 s t 的路径。

输出格式

输出一个整数,代表从 s t 的最短路长度。

数据范围与提示

n \leq 10^5, m \leq 2 \times 10^5, s,t,u_i,v_i \in [1,n], w_i \geq 0, \sum{w_i} \leq 10^8

如果用SPFA及其优化算法AC了本题(堆优化SPFA除外,因为它在非负权图下和Dijkstra算法是等价的),请将解题算法以及hack方法(如果能提供的话)发至594422141[at]qq.com,以便管理员加强数据。

数据更新后提交记录可能会不定时进行重测(为减轻评测机负担,应该会只重测AC的提交)。