题目

• 有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:

• 输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N-1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出格式:

• 在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 30 1 1 201 3 2 300 3 4 100 2 2 202 3 1 20

输出样例:

3 40

思路

• 在邻接矩阵中有两个 一个是长度G 一个是收费cost

• 在dijkstra基础上，增加了cost的更新，以及路径长度相等时，选取最小cost

延伸思路

AC代码

/*! * \file 07-图6 旅游规划.cpp * * \author ranjiewen * \date 2017/04/29 15:22 * *  *//*图的邻接矩阵表示法*/#include
    
     #include
     
      #include 
      
       #include 
       
        using namespace std;#define ERROR -1#define MaxVertexNum 505#define  INFINITY  65535typedef int Vertex; /*用顶点下标表示顶点，为整型*/typedef int WeightType; /*边的权重类型为整型*/typedef char DataType; /*顶点存储的数据类型为字符型*//*边的定义*/typedef struct ENode *PtrToENode;struct ENode{    Vertex V1, V2;    WeightType Weight; /*长度*/    WeightType cost;   /*过路费*/};typedef PtrToENode Edge;/*图节点的定义*/typedef struct GNode *PtrToGNode;struct GNode{    int Nv;    int Ne;    WeightType G[MaxVertexNum][MaxVertexNum]; /*邻接矩阵存放路径长度*/    WeightType cost[MaxVertexNum][MaxVertexNum]; /*邻接矩阵存放过路费*/    /*注意：很多情况下，顶点无数据，此时Data[]可以不用出现*/};typedef PtrToGNode MGraph;MGraph CreateMGraph(int VertexNum){    /*初始化一个有VertexNum个顶点但没有边的图*/    Vertex V, W;    MGraph Graph;    Graph = (MGraph)malloc(sizeof(struct GNode));    Graph->Ne = 0;    Graph->Nv = VertexNum;    /*初始化邻接矩阵*/    /*注意：这里默认顶点编号从0开始，到（Graph->Nv-1）*/    for (V = 0; V < Graph->Nv;V++)    {        for (W = 0; W < Graph->Nv;W++)        {            Graph->G[V][W] = INFINITY;            Graph->cost[V][W] = INFINITY;        }    }    return Graph;}void InsertMEdge(MGraph Graph, Edge E){    /*插入边
        
         */    Graph->G[E->V1][E->V2] = E->Weight;    Graph->cost[E->V1][E->V2] = E->cost;    /*若是无向图，还要插入边*/    Graph->G[E->V2][E->V1] = E->Weight;    Graph->cost[E->V2][E->V1] = E->cost;}MGraph BuildMGraph(int Nv, int Ne){    MGraph Graph;    Edge E;    Vertex V;    Graph = CreateMGraph(Nv);/*初始化有Nv个顶点但没有边的图*/    Graph->Ne = Ne;    if (Graph->Ne!=0)    {        E = (Edge)malloc(sizeof(struct ENode));        /* 读入边，格式为"起点 终点 长度 收费额"，插入邻接矩阵 */        for (int i = 0; i < Graph->Ne;i++)        {            scanf("%d %d %d %d", &E->V1, &E->V2, &E->Weight, &E->cost);            InsertMEdge(Graph, E);        }    }    return Graph;}//从未被收录顶点中找到dist最小者Vertex FindMinDist(MGraph Graph, int dist[], int collected[]){    Vertex MinV, V;    int MinDist = INFINITY;    for (V = 0; V < Graph->Nv;V++)    {        if (collected[V]==false&&dist[V]
         
          Nv;V++) { dist[V] = Graph->G[S][V]; path[V] = -1; collected[V] = false; cost[V] = Graph->cost[S][V]; } /*先将起点收入集合*/ dist[S] = 0; cost[S] = 0; collected[S] = true; while (1) { /*V=未被收录顶点中dist最小者*/ V = FindMinDist(Graph, dist, collected); if (V==ERROR) { break; //这样的V不存在，跳出循环 } collected[V] = true; //收录到集合中 for (W = 0; W < Graph->Nv;W++) { /*若V是W的邻接点并且未被收录*/ if (collected[W]==false&&Graph->G[V][W]
          
           G[V][W]<0) { return false; //有负边，返回错误 } /*若收录V使得dist[]变小*/ if (dist[V]+Graph->G[V][W]
           
            G[V][W]; //更新dist[W] path[W] = V; //更新S到W的路径 cost[W] = cost[V] + Graph->cost[V][W]; } else if (dist[V]+Graph->G[V][W]==dist[W]) { if (cost[W]>cost[V]+Graph->cost[V][W]) { cost[W] = cost[V] + Graph->cost[V][W]; path[W] = V; //更新路径 } } } } //end for } /* while结束*/ return true;}int main(){ //顶点数N城市数 边数M公路数 出发地S 目的城市D int N, M, S, D; cin >> N >> M >> S >> D; MGraph graph; graph = BuildMGraph(N, M); WeightType dist[MaxVertexNum] = { INFINITY }; WeightType cost[MaxVertexNum] = { INFINITY }; WeightType path[MaxVertexNum] = { 0 }; int collected[MaxVertexNum] = { false }; Dijkstra(graph, dist, cost, path, S); cout << dist[D] << " " << cost[D] << endl; return 0;}
           
          
         
        
       
      
     
    

Reference