Code for https://stackoverflow.com/q/77232598/16582

so77232598.cpp

#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include "../PathFinder/src/GraphTheory.h"

class cPirateIslands
{

public:
    // typedef std::vector<std::pair<std::string, int>> safePath_t;
    typedef raven::graph::path_cost_t path_t;

    void addAdjacentIslands(
        const std::string &name1,
        const std::string &name2,
        int cost)
    {
        int ei = gd.g.add(name1, name2);
        if (ei >= gd.edgeWeight.size())
            gd.edgeWeight.resize(ei + 1);
        gd.edgeWeight[ei] = cost;
    }
    void addPirate(
        const std::string &isle,
        int time)
    {
        vPirate.push_back(
            std::make_pair(gd.g.find(isle), time));
    }
    void setBoat(
        const std::string &dep,
        const std::string &dst)
    {
        gd.startName = dep;
        gd.endName = dst;
    }

    void generateExample1()
    {
        addAdjacentIslands("isle1", "isle2", 6);
        addAdjacentIslands("isle2", "isle3", 1);
        addAdjacentIslands("isle2", "isle4", 2);
        addAdjacentIslands("isle3", "isle4", 3);

        addPirate("isle3", 6);
        addPirate("isle3", 7);
        addPirate("isle3", 8);

        setBoat("isle1", "isle3");
    }

    void generateExample2()
    {
        addAdjacentIslands("isle1", "isle2", 6);
        addAdjacentIslands("isle1", "isle3", 1);
        addAdjacentIslands("isle2", "isle4", 2);
        addAdjacentIslands("isle3", "isle4", 3);

        addPirate("isle3", 1);
        addPirate("isle3", 2);
        addPirate("isle3", 3);
        addPirate("isle3", 4);
        addPirate("isle3", 5);

        setBoat("isle1", "isle4");
    }

    /// @brief find path between start and end islands that avoids pirates

    void solve()
    {
        // apply dijsktra
        path_t pth = path(gd);

        // dodge pirates
        bool fPirateDelay = false;
        mySafePath = dodgePirates(
            pth,
            fPirateDelay);

        if (!fPirateDelay)
            return;

        // there was a pirate delay,
        // check alternate paths from Yen's algorithm
        std::cout << "Check alternative path\n";
        auto bestPath = mySafePath;
        bool first = true;
        for (auto &pathtest : allPaths(gd))
        {
            if (first)
            {
                first = false;

                // ignore first path from Yen, it is the dijsktra path
                continue;
            }

            // dodge pirates
            mySafePath = pathtest;
            bool fPirateDelay = false;
            mySafePath = dodgePirates(
                mySafePath,
                fPirateDelay);

            // check for better path
            if (mySafePath.second < bestPath.second)
            {
                bestPath = mySafePath;
                std::cout << "better path: more sailing less pirates\n";
            }

            // check for no pirate delays
            // in which case there is no expectation of finding a better path
            // since the rest of the possible paths are longer, even with no pirate delays
            if (!fPirateDelay)
                break;
        }

        // keep the best path found
        mySafePath = bestPath;
    }

    void printSafePath() const
    {
        int prev = -1;
        int time = 0;
        for (int isle : mySafePath.first)
        {
            if (prev == -1)
            {
                std::cout << "\nat time " << time << " " << gd.g.userName(isle) << "\n";
                prev = isle;
                continue;
            }
            if (isle == prev)
            {
                std::cout << "staying ";
                time++;
                prev = isle;
                continue;
            }
            for (
                int sailtime = gd.edgeWeight[gd.g.find(prev, isle)];
                sailtime;
                sailtime--)
            {
                std::cout << "sailing ";
                time++;
            }
            std::cout << "\nat time " << time << " arrive " << gd.g.userName(isle) << "\n";
            prev = isle;
        }
    }

private:
    raven::graph::sGraphData gd; // island adjacencies

    std::vector<std::pair<int, int>> vPirate; // pirate locations

    path_t mySafePath;

    bool isPirateCollision(
        int isle,
        int time)
    {
        return std::find(
                   vPirate.begin(), vPirate.end(),
                   std::make_pair(isle, time)) != vPirate.end();
    }

    /// @brief wait for pirates, if encountered on island
    /// @param[in/out] safePath
    /// @param prev
    /// @param isle // to check
    /// @param[in/out] // in: time we would arrive with no pirates, out: time actually arrived
    /// @return true if pirates caused delay

    bool waitForPirates(
        path_t &path,
        int prev,
        int isle,
        int &time)
    {
        bool ret = false;
        while (isPirateCollision(isle, time))
        {
            ret = true;
            std::cout << "Pirates on " << gd.g.userName(isle) << " staying on ";
            atIsland(
                path,
                prev,
                time);
            time++;
            path.second++;
        }
        return ret;
    }
    path_t
    dodgePirates(
        path_t &nodelay,
        bool &fPirateDelay)
    {
        fPirateDelay = false;
        int time = 0;
        auto prev = nodelay.first.end();
        path_t safePath;

        // loop over path
        for (
            auto it = nodelay.first.begin();
            it != nodelay.first.end();
            it++)
        {
            if (prev == nodelay.first.end())
            {
                // at start island
                prev = it;
                atIsland(
                    safePath,
                    *it,
                    time);
                continue;
            }

            // calculate the time
            int isle = *it;
            int sailtime = gd.edgeWeight[gd.g.find(*prev, isle)];
            time += sailtime;
            safePath.second += sailtime;

            // wait until island is free of pirates
            bool delayed = waitForPirates(
                safePath,
                *prev,
                isle,
                time);
            if (!fPirateDelay)
                fPirateDelay = delayed;

            // safe to move on
            atIsland(
                safePath,
                isle,
                time);

            prev = it;
        }
        return safePath;
    }

    void atIsland(
        path_t &safePath,
        int isle,
        int time)
    {
        auto name = gd.g.userName(isle);
        std::cout << name << " at time " << time << "\n";
        safePath.first.push_back(isle);
    }
};

main()
{
    cPirateIslands thePirateIslands;

    thePirateIslands.generateExample2();

    thePirateIslands.solve();

    thePirateIslands.printSafePath();

    return 0;
}