Problem 2964 --Path

2964: Path

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $53$ 正确数量 $6$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
Years later, Jerry fell in love with a girl, and he often walks for a long time to pay visits to her. But, because he spends too much time with his girlfriend, Tom feels neglected and wants to prevent him from visiting her.
After doing some research on the neighbourhood, Tom found that the neighbourhood consists of exactly n houses, and some of them are connected with directed road. To visit his girlfriend, Jerry needs to start from his house indexed 1 and go along the shortest path to hers, indexed n.
Now Tom wants to block some of the roads so that Jerry has to walk longer to reach his girl's home, and he found that the cost of blocking a road equals to its length. Now he wants to know the minimum total cost to make Jerry walk longer.
Note, if Jerry can't reach his girl's house in the very beginning, the answer is obviously zero. And you don't need to guarantee that there still exists a way from Jerry's house to his girl's after blocking some edges.
The input begins with a line containing one integer T(1≤T≤10), the number of test cases.
Each test case starts with a line containing two numbers n,m(1≤n,m≤10000), the number of houses and the number of one-way roads in the neighbourhood.
m lines follow, each of which consists of three integers x,y,c(1≤x,y≤n,1≤c≤10^9), denoting that there exists a one-way road from the house indexed x to y of length c.
Print T lines, each line containing a integer, the answer.
1
3 4
1 2 1
2 3 1
1 3 2
1 3 3
3

推荐代码 查看2964 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$48 $ms] llmxby 470044 2019-09-19 11:24:39
内存最少[$3128 $KB] Camel 902168 2022-10-14 11:27:54
第一AC 刘成健 450721 2019-08-02 19:59:07
第一挑战 槑槑 449440 2019-07-26 22:43:25

赛题来源/所属竞赛 2019 Multi-University Training Contest 1 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛
1407 2019CCPC模拟赛(秦皇岛站 安财贸9.19) 2019-09-19 09:00:00 请登录