#1316. 单源最短路

单源最短路

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个无向图。

求有 A\red{A} 点到 B\red{B} 点的最短路径。

输入格式

第一行 四个数,n,m,a,b\red{n,m,a,b}

n\red n个顶点

m\red m条边

a\red a为起点

b\red b为终点

接下来2m+1\red {2 \sim m+1} 行,每行3\red 3个正整数。代表v\red vu\red u的权值是w\red w

输出格式

一个数,表示 a\red{a}b\red{b} 的最短路

样例

输入样例

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

输出样例

7

数据范围与提示

1n2500\red{1 \le n \le 2500}

1m6200\red{1 \le m \le 6200}

1a,bn\red{1 \le a,b \le n}

少年宫周五高级班期末测试

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-12-15 19:00
结束于
2023-12-15 21:00
持续时间
2 小时
主持人
参赛人数
9