公交线路最短路径查询

最短路径问题是图论中的一个经典问题，其中的Dijkstra算法一直被认为是图论中的好算法，但有的时候需要适当的调整Dijkstra算法才能完成多种不同的优化路径的查询。 对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。设该城市的公交线路的输入格式为： 线路编号：起始站名(该站坐标)；经过的站点1名(该站坐标)；经过的站点2名(该站坐标)；……；经过的站点n名(该站坐标)；终点站名(该站坐标)。该线路的乘坐价钱。该线路平均经过多少时间来一辆。车速。 例如：63：A(32,45)；B(76,45)；C(76,90)；……；N(100,100)。1元。5分钟。1/

#include
#include
#include
#include
using namespace std;

#define NoEdge 99999//无路线

int number;//公交线路数
int count=0;//多次出现的地点数
int *area;

double *price;//车票价格数组
int *speed;//车速数组

double **DistanceMap;//以距离为权值的邻接矩阵
double **PriceMap;//以票价为权值的邻接矩阵
double **TimeMap;//以时间为权值的邻接矩阵

int *numIndex;//车站编号索引
string *nameIndex;//车站姓名索引
int *priceIndex;//票价索引
int *lpriceIndex;//处理后的票价
int range;//总车站数

double Restrict（double a）//double保留两位小数方法
{
    double tem=int（a*100）;
    return tem/100;
}

double getDistance（double adouble bdouble cdouble d）//求两点间距离方法
{
    return Restrict（sqrt（（a-c）*（a-c）+（b-d）*（b-d）））;
}

class RChainNode//链表结点类
{
    friend class BusRoutine;
    friend class RChain;
public:
    string station;
    double px;
    double py;
    RChainNode *next;
    RChainNode *prior;
};

class RChain//链表类
{
    friend class BusRoutine;
public:
    RChain（）//构造函数 
    {
        first = 0;
    }
    ~RChain（）;//析构函数 

    bool IsEmpty（）
    {

        return first == 0;
    }
    int Length（） const;

    RChainNode *getFirst（）//得到链表头结点
    {

        return first;
    }
    RChain &Insert（const string &s const double &xconst double &y）;
    RChain &IInsert（RChainNode *rn）;
    void Output（ostream &out） const;

    string getStation（）//返回站点名
    {

        return first->station;
    }
    RChain &Rearrange（double &y）;
    RChain &reCharge（RChain &r）;
    RChain &dRejudge（）;
private:
    RChainNode *first;
};

RChain::~RChain（）//在类外声明析构函数 
{
    RChainNode *next;
    while （first）
    {
        next = first->next;
        delete first;
        first = next;
    }

}

int RChain::Length（） const//Length（）是属于RChain类的，可以引用，但不能修改本类中的数据成员 
{
    RChainNode *current = first;
    int len = 0;
    while （current）
    {
        len++;
        current = current->next;
    }
    return len;
}

RChain &RChain::Insert（const string &s const double &x const double &y）//从后插入新结点
{
    if （!first）
    {
        first = new RChainNode;
        first->station = s;
        first->px = x;
        first->py = y;
        first->next = 0;
        first->prior = 0;
    }
    else
    {
        RChainNode *p = first;
        while （p->next）
            p = p->next;
        RChainNode *r = new RChainNode;
        r->station=s;
        r->px = x;
        r->py = y;
        p->next = r;
        r->prior = p;
        r->next=0;

    }//插入在表尾，形成类似与C1C2C3C4...Cn的链表 
    return *this;
}

RChain &RChain::IInsert（RChainNode *rn）//从后插入一个已有结点
{
    if（first）
    {
        RChainNode *tem=rn;
        RChainNode *p = first;
        while （p->next）
            p = p->next;
        p->next=tem;
        tem->prior=p;
    }
    else
        first=rn;
}

RChain &RChain::Rearrange（double &y）//将车站链表处理，得到距离及对应累加序号
{
    RChainNode *Current=first;
    for（Current; Current->next; Current=Current->next）