Pathfind.hpp

#ifndef PATHFIND_H
#define PATHFIND_H
#include <bits/stdc++.h>
#include "Metrograph.hpp"
using ll = long long;
using ld = long double;
const double INF = 0x3f3f3f3f3f3f3f3f;
/*
由于手上已经有了dijkstra的板子,而地铁换乘等需要考虑时间因素和距离的多维因素而不是一维的距离因素
基于奥卡姆剃刀原理，设计一个 权重计算函数,使得我们可以继续使用原有的dijkstra板子.
记录路径，否则会丢失换乘信息...(用栈)
为了便于计算，将换乘惩罚设定为200s
*/
struct Node{
    double cost;
    int line_u;int line_in;
    //重载实现小根堆
    bool operator>(const Node& other) const{
        return this -> cost > other.cost;
    }
};
struct PathRecord{
    int parent;int line;
};
class PathFind{
    private:
    const MetroGraph* graph;//指向图的指针
    std::vector<double> dis;
    std::vector<bool> vis;
    std::vector<PathRecord> PathNote;
    
    //权重计算函数(不仅要考虑路径长短换乘时长，还要考虑乘客的喜好模式)
    double cal_w(int LineIn,const Edge& LineOut,const std::string& mode);
        

    public:
    std::string GetPathString(int start, int end);
    PathFind(const MetroGraph* g);//构造函数，参数为g
    //根据选定模式进行dijkstra寻路
    bool dijkstra(int start,int end,std::string mode);
    //打印路径
    void PrintPath(int start,int end);
};



#endif