Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.programming Subject: Re: Problem C++ gas tank refuel Date: Tue, 21 Dec 2021 08:55:46 -0800 Organization: A noiseless patient Spider Lines: 17 Message-ID: <86r1a528z1.fsf@linuxsc.com> References: <8fd306f3-1cdc-439b-a82c-458f9b926418n@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="0fbb3e029bf9991db82a5be437217d3c"; logging-data="21844"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+5u8jpDr7Lt0B+BPR6SUvxoiM6AI9+H2Q=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:/DE4B7u3wnC5PgHXblDsHdH04Kw= sha1:KjM/jnW7KJlBOuEiZmYaQ233VEE= Xref: csiph.com comp.programming:14354 Darioes writes: > Im programing a new exerciese that i need to do for a college > project, in C++. > > That project consists in implementing an algorithm that just goes > the minimal ways, not like Dijkstra's algorithm but something > similar: You are have a car, that needs to go from France to Corea > and you need to refil your gas tank . You need to pick the minimal > ways so that the car's fuel tank is as low as possible. Assuming that I understand correctly what you are looking for, this problem is a standard graph shortest path problem. The only difference is adding a new link to a path uses MAX rather than addition. The "distances" involved are still monotonic, so the conventional algorithm works, just using MAX rather than plus.