I've had a bit of wine so I missed the initial start by a little bit for this one. Oops. But it looks like it's finally path solving!

... Although this time it looks like it is absolutely more complicated than just re-implementing A*. There's two kinds of nodes ("caves"), and they need to be treated differently; one kind only visiting once, the other can be visited as many times as necessary. This doesn't seem too tricky, but does involve a lot of double-checking. Judging by the example paths given, they are giving a depth-first search as an example.

So with that! I'm thinking a dictionary that has FROM every cave, every other cave they connect to, going both ways. There's a recursive call going from the 'start' node to the 'end' node, and it'll call into every cave that is in the dictionary for each node. For the small caves (using lowercase letters) check if it already exists in the current path, and prune that branch if it's already in the existing path.

My main concern is that there might be an infinite loop if there's a pair of large caves adjacent to each other? But looking at the inputs, that's not a big concern.

bool isSmall(string cave) { return (cave[0] >= 'a' && cave[0] <= 'z'); }

vector<vector<string>> nextPaths(CAVES caves, vector<string> path) {
    vector<vector<string>> nextSteps;

    for (auto neighbor: caves[path.back()]) {
        if (!isSmall(neighbor)
            || (isSmall(neighbor) && (find(path.begin(), path.end(), neighbor) == path.end()))
        ) {
            vector<string> nextStep = vector<string>(path);
            nextStep.push_back(neighbor);
            nextSteps.push_back(nextStep);
        }
    }

    return nextSteps;
}

vector<vector<string>> fullPaths;
queue<vector<string>> toCheck;
vector<string> startPath;
startPath.push_back("start");
toCheck.push(startPath);

while (!toCheck.empty()) {
    vector<string> curPath = toCheck.front();
    toCheck.pop();

    if (curPath.back() == "end") {
        fullPaths.push_back(curPath);
    } else {
        vector<vector<string>> next = nextPaths(caves, curPath);
        for (auto path: next) toCheck.push(path);
    }
}

Okay, so I implemented breadth-first search instead. It still gives the same results though, and it worked first try unbelieveably enough!

Looks like small caves can be visited twice!

bool canVisit(vector<string> path, string cave) {
    if (cave == "start") return false;
    if (!isSmall(cave)) return true;

    int visitCount = 0;
    for (auto c: path) {
        if (c == cave) visitCount++;
        if (visitCount >= 2) return false;
    }

    return true;
}

Hmm... nope... that returns way too many caves.

... Oh! ONE small cave may be visited twice. Oh. This is going to be a bit more complex.

bool canVisit(vector<string> path, string cave) {
    if (cave == "start") return false;
    if (!isSmall(cave)) return true;

    map<string, bool> visited;
    bool extraVisitUsed = false;
    visited[cave] = true;
    for (auto c: path) {
        if (!isSmall(c)) continue;
        if (visited[c]) {
            if (extraVisitUsed) return false;
            extraVisitUsed = true;
        } else {
            visited[c] = true;
        }
    }

    return true;
}

That took a bit more figuring out than usual, and it took a few seconds to run to completion, but I got the right answer after some tweaking!