如何用dp解决HDU 3790的双重权值最短路径问题？

本文共计935个文字，预计阅读时间需要4分钟。

题目：最短路径问题

时间限制：2000/1000ms（Java/其他）

内存限制：32768/32768K（Java/其他）

总提交次数：19

已接受提交次数：5

问题描述：给定n个点，m条无向边，每条边都有长度d和花费p，求从一个点出发到另一个点的最短路径。

最短路径问题

Time Limit : 2000/1000ms (Java/Other)Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 19Accepted Submission(s) : 5

Problem Description

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

Input

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。