算法思想：将信息存储为邻接表。由于连续小道长度的不同，将点拆为不同的若干点。运用小项堆优化的 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 }