大疆笔试-最少充电时间

题目很复杂，但是直接暴力dfs就行

注意递归条件，要考虑到每一种充电时间

本来想记忆化一下，没想到暴力直接A了

#include<map>
#include<vector>
#include<iostream>
using namespace std;


class Solution {
public:
    map<int,vector<pair<int,int>>> disMap;
    int maxResult=100086;
    void getResult(int allCost,int nowCharge,int dis,int now,int target,vector<int>charge,vector<bool>&visit,vector<vector<int>>&dp){
        if(now==target){
            maxResult=maxResult>allCost?allCost:maxResult;
            return;
        }
        for(auto p:disMap[now]){
            int next=p.first;
            int nextDis=p.second;
            if(visit[next]){
                continue;
            }
            visit[next]=true;
            int leastDis=0;
            // 至少要充一下电，保证有电上路
            if(nextDis>nowCharge){
                leastDis=(nextDis-nowCharge)*charge[now];
            }
            // 1. 开始遍历各种充电方案
            int maxV=nextDis>nowCharge?nextDis:nowCharge;
            for(int i=dis;i>=maxV;i--){
			  //allCost+leastDis+(i-maxV)*charge[now]+nextDis
			  //—— leastDis：最少充电时间
			  //——i-maxV：多冲的千米数
			  //——nextDis：跑到下一个点花的时间
                getResult(allCost+leastDis+(i-maxV)*charge[now]+nextDis,i-nextDis,dis,next,target,charge,visit,dp);
            }
            visit[next]=false;
        }
    }
    int car_plan(vector < vector < int > > paths, int dis, int a, int b, vector < int > charge) {
        if(a==b){
            return 0;
        }
        int n=paths.size();
        for(int i=0;i<n;i++){
            int s=paths[i][0];
            int e=paths[i][1];
            int dis=paths[i][2];
            disMap[s].push_back({e,dis});
            disMap[e].push_back({a,dis});
        }
        int m=charge.size();
        vector<vector<int>>dp(n,vector<int>(n,0x3f3f3f3f));
        vector<bool>visit(m,false);
        visit[a]=true;
        getResult(0,0,dis,a,b,charge,visit,dp);
        return maxResult;
    }
};
int main() {
    int res;


    int paths_rows = 0;
    int paths_cols = 0;
    cin >> paths_rows >> paths_cols;
    vector< vector < int > > paths(paths_rows);
    for(int paths_i=0; paths_i<paths_rows; paths_i++) {
        for(int paths_j=0; paths_j<paths_cols; paths_j++) {
            int paths_tmp;
            cin >> paths_tmp;
            paths[paths_i].push_back(paths_tmp);
        }
    }
    int dis;
    cin >> dis;






    int a;
    cin >> a;






    int b;
    cin >> b;






    int charge_size = 0;
    cin >> charge_size;


    vector<int> charge;
    int charge_item;
    for(int charge_i=0; charge_i<charge_size; charge_i++) {
        cin >> charge_item;


        charge.push_back(charge_item);
    }




    Solution *s = new Solution();
    res = s->car_plan(paths, dis, a, b, charge);
    cout << res << endl;


    return 0;


}
'''