寻找“都是英里数”的线索

Question

我最近遇到一个问题，我真的不知道怎么解决它。这是开卡蒂斯的问题。你知道吗

请访问https://uchicago.kattis.com/problems/uchicago.miles

现在，我知道这是一个递归问题。你知道吗

但是如何定义这个递归过程呢？我不知道从哪里开始。你知道吗

所以请给我一个线索或者一些伪代码。你知道吗

在这里，我粘贴了用于读取输入的代码，并将输入数据转换为字典。你知道吗

AFItt = input().split()
A, F, I = map(int, AFItt[0:3])
tmin, tmax = map(float, AFItt[3:])
airport = []
ada ={}
ai= []

for _ in range(A):
    airport.append(input())

for _ in range(F):
    ffda = input().split()
    if ffda[0] + " " + ffda[1] not in ada.keys():
        ada[ffda[0] + " " + ffda[1]] = (float(ffda[2]), float(ffda[3]))
    else:
        ada[ffda[0] + " " + ffda[1]] += ((float(ffda[2]), float(ffda[3])))

for _ in range(I):
    ai.append(input())

Answer 1

我会尽量给你一个线索，但不确定它是否足够有效。我编写了一个javascript版本，它可以正确地生成示例输出。你知道吗

我的解决方案非常简单：从行程开始，找到所有可能的下一个航班，并继续附加到以前的航班运行。你知道吗

例如

for first 2 itinerary airports，我将找到所有可能的航班并将其保存在数组列表中[[fligh1], [flight2], [flight3]]

在那之后，我将循环当前所有可能的运行，并继续检查是否有可能继续运行的航班存在。如果不是，则排除在外，如果是，则将航班添加到列表中。你知道吗

如果flight1和flight2无法继续，但flight3有两个可能的航班要继续，我的航班列表将更改为[[flight3, flight4], [flight3, flight5]]

我很难解释清楚。以下是一些代码框架：

function findAllFlights(flightMap, 
                        currentFlights, 
                        currentItineraryIndex, 
                        itineraryList, minTime, maxTime){
    //flightMap is a map of all the flights. sample data:
    /*{'a->b':[{from: 'a', to:'b', depTime:'1', arrTime:'2'}, {another flight}, ... ],
       'b->c': [{from: 'b', to:'c', depTime:'1', arrTime:'2'}, {another flight}, ... ]}
    */ 

    //currentFlights is the result of current possible runs, it is a list of list of flights. each sub list means a possible run.
    //[[flight1, flight2], [flight1, flight3], ...]

    //currentItineraryIndex: this is the next airport index in the itineraryList
    //itineraryList: this is the list of airports we should travel.
    //minTime, maxTime: it is the min time and max time.

    if(currentItineraryIndex == 0){
        var from = itineraryList[0];
        var to = itineraryList[1];
        var flightMapKey = from+'->'+to;
        var possibleFlights = flightMap[flightMapKey];
        if(possibleFlights.length == 0){
            return [];
        }
        for(var i=0; i<possibleFlights.length; i++){
            //current flights should be a list of list of flights.
            //each of the sub list denotes the journey currently.
            currentFlights.push([possibleFlights[i]]);
        }
        return findAllFlights(flightMap, currentFlights, 1, itineraryList, minTime, maxTime);
    }else if(currentItineraryIndex == itineraryList.length - 1){
        //we have searched all the required airports
        return currentFlights;
    }else{
        //this is where you need to recursively call findAllFlights method.
        var continableFlights = [];
        //TODO: try to produce the continuable list of flights here based on above explanation.
        //once we have the continuable flights for current itinerary airport, we can find flights for next airport similarly.
        return findAllFlights(flightMap, continableFlights, currentItineraryIndex + 1, itineraryList, minTime, maxTime);
    }
}

好好享受！你知道吗