力扣2662. 前往目标的最小代价

力扣2662. 前往目标的最小代价

题目

题目解析及思路

题目要求返回从start到target的最小代价，其中有若干条特殊路径

最短路径一定是从st->特殊点->…->特殊点->target

用特殊点建图然后bfs

代码

class Solution {
public:
    int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
        typedef pair<int, int> PII;
        map<PII,int> mp;
        //将(x,y)入图
        auto add = [&](int x,int y){
            PII p = PII(x,y);
            if(mp.count(p)) return;
            int idx = mp.size();
            mp[p] = idx;
        };

        //将start和target入图
        add(start[0],start[1]);
        add(target[0],target[1]);

        //将特殊路径入图
        for(auto road:specialRoads){
            add(road[0],road[1]);
            add(road[2],road[3]);
        }

        int n = mp.size();
        //将每个特殊点的坐标存下来
        int X[n],Y[n];
        for(auto it = mp.begin();it != mp.end();it ++){
            X[it->second] = it->first.first;
            Y[it->second] = it->first.second;
        }

        //建图
        vector<int> e[n];
        vector<long long> v[n];

        //任意两点可以互相到达
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i != j){
                    e[i].push_back(j);
                    v[i].push_back(abs(X[i] - X[j]) + abs(Y[i] - Y[j]));
                }
            }
        }

        //n条特殊路径，额外加上
        for(auto road : specialRoads){
            int sn = mp[PII(road[0],road[1])];
            int fn = mp[PII(road[2],road[3])];
            e[sn].push_back(fn);
            v[sn].push_back(road[4]);
        }

        //从S到T
        int S = mp[PII(start[0],start[1])] ,T = mp[PII(target[0],target[1])];
        long long dis[n];
        memset(dis,-1,sizeof(dis));
        typedef pair<long long,int> PLI;
        //默认是个大顶堆，存路径的时候得加个负号，可以改成小顶堆就不用加了
        priority_queue<PLI> pq;
        //first存路径长度，second存当前点的编号
        pq.push(PLI(0,S));

        while(pq.size()){
            PLI p = pq.top();
            pq.pop();
            int sn = p.second;
            long long d = -p.first;
            //防止重复遍历
            //如果dis>=0，说明已经被更新过，是最短的，不需要再更新了
            if(dis[sn] >= 0) continue;
            //取出说明sn的dis值是最短的了
            dis[sn] = d;
            //枚举连接的其他点
            for(int i=0;i<e[sn].size();i++){
                int fn = e[sn][i];
                if(dis[fn] >= 0) continue;
                //因为是大顶堆，所以边权都加个负号
                pq.push(PLI(-d-v[sn][i],fn));
            }
        }
        return dis[T];
    }
};