2982:Time Travel

题目描述

According to Professor Canaried’s recent theory about space and time, our universe is like a piece of plane paper with infinite length and finite width, if we consider time as X-dimension of plane and space as Y-dimension. Outside the boundary of our universe are dangerous unknown spaces, which once people reach, he/she can never come back to our universe. People cannot go back to the foretime but can go forward to the future freely.

Dagger is now at time0 and position0, she wants to move to timeN and positionM. Time Travel Company supplies K various services; each can be described as three integers a, b, c, which means if you are at timeX and positionY now, you can move to timeX + a and positionY + b for c Gils’ cost. Your task is to find the minimal cost for Dagger to move to timeN and positionM. The costs are always positive.

输入解释

There are several test cases in the input. Each test case starts with three integers N (0 < N ≤ 100), M (0 < M ≤ 100) and K (0 ≤ K ≤ 100). The Next K lines each contains three integers a, b, c. N = M = K = 0 indicates the end of the input which should not be processed.

输出解释

Output one line for each test case in the input, the minimal cost. Output −1 if it is impossible to move to the destination.

输入样例
4 6 3
4 6 100
1 5 10
3 1 20
0 0 0
输出样例
30

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-2982

最后修改于 2020-10-29 06:49:05 UTC 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 131072

·

·

·

·

登陆或注册以提交代码