行车路线

算法思想：将信息存储为邻接表。由于连续小道长度的不同，将点拆为不同的若干点。运用小项堆优化的 dijkstra对由1到不同点的最小疲劳值进行更新，同时用path和continuelength分别记录优化后节点对应上一个结点的数据（点标号和连续小路）。最后在每个点的所有拆点中找出最小的路径输出，对于n一次次向前（利用该节点存储的上一个结点的信息）推得出最短路径。

主要/核心函数分析：//堆优化版dijkstravoid dijkstra()初始化dist数组（储存不同的拆点x到1的最短疲惫值）。从1开始（此时1点的连续小路为0，最短疲惫值为0）对与它相连的点进行遍历，如果经过1的疲惫值比原先的要小，就更新dist对应的拆点，同时将该拆点的数据存入小项堆，依次取出堆中元素对dist进行更新，直到堆中没有元素。

测试数据：

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

运行结果：

到1最小疲劳值0

到2最小疲劳值9

到3最小疲劳值25

到4最小疲劳值45

到5最小疲劳值66

到6最小疲劳值76

最短路径为:

6 5 4 3 2 1

  1 #include <iostream>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <queue>
  5 #include <fstream>
  6 
  7 using namespace std;
  8 
  9 const int N = 510, M = 200010, INF = 0x3f3f3f3f;
 10 int h[N],                    e[M],          w[M], tag[M], ne[M],        idx;
 11 //以该顶点为起点的边的编号，该编号边的终点，权重，类型，与该边关联的边，编号
 12 int dist[N][1010];//连续小道的长度之和一定不会超过1000。
 13 //dist[i][j]——表示从1号点走到第i号点，路径包含最后一段是连续小道的总长度为j的最短路径
 14 bool st[N][1010];//点的去重标记也跟随拆点
 15 int path[N][1010];//记录连续长度为j时的前驱节点
 16 int continuelength[N][1010];//记录连续长度为j的前驱节点的最短路径的连续长度
 17 int n, m;//点数和边数
 18 
 19 //邻接表
 20 void add(int t, int a, int b, int c) 
 21 {
 22     e[idx] = b, w[idx] = c, tag[idx] = t, ne[idx] = h[a], h[a] = idx++;
 23 }
 24 
 25 struct Node 
 26 {//拆点，由于y的不同，x号点被拆成若干点
 27     int x, y, d;//y是小道的连续长度，d为最短疲惫
 28     bool operator<(const Node& p)const 
 29     {
 30         return d > p.d;
 31     }
 32 };
 33 
 34 //堆优化版dijkstra
 35 void dijkstra() 
 36 {
 37     priority_queue<Node> heap;//priority_queue默认大根堆，由于Node内置排序为降序，因此实际意义还是小根堆
 38     heap.push({ 1,0,0 });
 39     memset(dist, 0x3f, sizeof dist);
 40     dist[1][0] = 0;
 41     while (heap.size()) 
 42     {
 43         Node t = heap.top();
 44         heap.pop();
 45 
 46         //已经访问
 47         if (st[t.x][t.y])continue;
 48 
 49         st[t.x][t.y] = true;//标记，将该点拆开来
 50 
 51         //访问与t.x相邻的点
 52         for (int i = h[t.x]; i != -1; i = ne[i]) 
 53         {
 54             int k = e[i], weight = w[i];
 55             if (tag[i]) 
 56             {//小路
 57                 if (t.y + weight <= 1000)//连续小道的长度之和一定不会超过1000
 58                     if (dist[k][t.y + weight] > t.d - t.y * t.y + (t.y + weight) * (t.y + weight)) 
 59                     {
 60                         dist[k][t.y + weight] = t.d - t.y * t.y + (t.y + weight) * (t.y + weight);
 61                         if (dist[k][t.y + weight] <= INF) heap.push({ k,t.y + weight,dist[k][t.y + weight] });
 62                         path[k][t.y + weight] = t.x;
 63                         continuelength[k][t.y+weight] = t.y;
 64                     }
 65             }
 66             else 
 67             {//大路
 68                 if (dist[k][0] > t.d + weight) 
 69                 {
 70                     dist[k][0] = t.d + weight;
 71                     if (dist[k][0] <= INF) heap.push({ k,0,dist[k][0] });
 72                     path[k][0] = t.x;
 73                     continuelength[k][0] = t.y;
 74                 }
 75             }
 76         }
 77     }
 78 }
 79 
 80 int main() 
 81 {
 82     memset(h, -1, sizeof h);
 83 
 84     fstream fp;
 85     fp.open("test.txt", ios::in);
 86 
 87     fp >> n >> m;
 88 
 89     int t, a, b, c;
 90     while (m--) 
 91     {
 92         fp >> t >> a >> b >> c;
 93         //无向图
 94         add(t, a, b, c);
 95         add(t, b, a, c);
 96     }
 97     fp.close();
 98 
 99     dijkstra();
100 
101     vector<int>ans;
102     ans.push_back(0);
103     int nlianxu;
104     for (int j = 2; j <= n; j++)
105     {
106         int res = INF;
107         nlianxu = 0;
108         for (int i = 0; i <= 1000; i++)
109         {
110             if (res > dist[j][i])
111                 nlianxu = i;
112             res = min(res, dist[j][i]);
113         }
114         ans.push_back(res);
115     }
116 
117     for (int i = 0; i < n; i++)
118         cout << "到" << i + 1 << "最小疲劳值" << ans[i] << endl;
119 
120     cout << "最短路径为:" << endl;
121     int endknot = n;
122     while (path[endknot][nlianxu])
123     {
124         cout << endknot << " ";
125         int k = endknot;
126         endknot = path[k][nlianxu];
127         nlianxu = continuelength[k][nlianxu];
128     }
129     cout << 1;
130 }