本文共 2701 字，大约阅读时间需要 9 分钟。

• 数据结构课程设计

• 行车路线（图）

小明和小芳出去乡村玩，小明负责开车，小芳来导航。

小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s2的疲劳度。 例如：有5个路口，1号路口到2号路口为小道，2号路口到3号路口为小道，3号路口到4号路口为大道，4号路口到5号路口为小道，相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口，则总疲劳值为(2+2)2+2+22=16+2+4=22。 现在小芳拿到了地图，请帮助她规划一个开车的路线，使得按这个路线开车小明的疲劳度最小。 输入格式 输入的第一行包含两个整数n, m，分别表示路口的数量和道路的数量。路口由1至n编号，小明需要开车从1号路口到n号路口。 接下来m行描述道路，每行包含四个整数t, a, b, c，表示一条类型为t，连接a与b两个路口，长度为c公里的双向道路。其中t为0表示大道，t为1表示小道。保证1号路口和n号路口是连通的。 输出格式 输出一个整数，表示最优路线下小明的疲劳度。 样例输入 6 7 1 1 2 3 1 2 3 2 0 1 3 30 0 3 4 20 0 4 5 30 1 3 5 6 1 5 6 1 样例输出 76 样例说明 从1走小道到2，再走小道到3，疲劳度为52=25；然后从3走大道经过4到达5，疲劳度为20+30=50；最后从5走小道到6，疲劳度为1。总共为76。 数据规模和约定 对于30%的评测用例，1≤n≤8，1≤m≤10； 对于另外20%的评测用例，不存在小道； 对于另外20%的评测用例，所有的小道不相交； 对于所有评测用例，1≤n≤500，1≤m≤105，1≤a, b≤n，t是0或1，c≤105。保证答案不超过106。

• 分析

基本思想是使用迪杰斯特拉算法求解最短路径，

修改算法适应本题要求：

· 如果前面路径长度r1都是小路，下一条路径r2也是小路，

那么路径长度应该是(r1+r2)^2,而不是r1^2+r2^2

· 每次更新最短路径顶点集时，需要判断下一条时大路还是小路，从而进行不同方式的疲劳度增加。

过多的不多说了，注释比较明白了。

测试数据已给出，在程序最后

• Code，环境codeblocks17 通过

//@ChenYe 2018/12/27#include 
   
    #include 
    
     #include 
     
      // windows.h 和本代码有冲突，有待查明。。。#define green SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_GREEN|FOREGROUND_INTENSITY)#define white SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_BLUE|FOREGROUND_GREEN)#define red SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED|FOREGROUND_INTENSITY)// 类似green; red; white;的语句为颜色控制语句 windows.h 和本代码有冲突就不能用颜色控制了#define MAXSIZE 500const int INF = 0x3f3f3f3f;const int NINF = 0xc0c0c0c0;//1061109567, -1061109568using namespace std;long long big[MAXSIZE][MAXSIZE],small[MAXSIZE][MAXSIZE];   // 大路小路int vis_big[MAXSIZE], vis_small[MAXSIZE];   // 最短路径顶点集long long sr[MAXSIZE], br[MAXSIZE]; // 记录v0到各个顶点走大路或者小路的最短路径长度--权值long long path[MAXSIZE];//记录顶点v之前正在连续的>小路
      
       temp || (sr[j]==temp&&path[j]>(path[v]+small[v][j])))// 注意当temp和原路径长度相等时，如果path[j]>(path[v]+small[v][j])也进入if                    {                        sr[j] = temp;                        path[j] = path[v]+small[v][j];                    }                }                else    //prev到v之间是big road                {                    long long temp = br[v]+small[v][j]*small[v][j];                    if(sr[j] > temp || (sr[j] == temp && path[j] > small[v][j]))                    {                        sr[j] = temp;                        path[j] = small[v][j];                    }                }            }            if(!vis_big[j] && big[v][j]
       
        >n>>m;    for(long long i=0; i
        
         >t>>a>>b>>c; a--; b--; if(t==1) small[a][b] = small[b][a] = min(c,small[a][b]); else big[a][b] = big[b][a] = min(c,big[a][b]); } cout<<"the shortest path length is: "<
         
          <
         
        
       
      
     
    
   

 

转载地址：http://xjoen.baihongyu.com/