问题描述
小明和小芳出去乡村玩，小明负责开车，小芳来导航。
小芳将可能的道路分为大道和小道。大道比较好走，每走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。
现在小芳拿到了地图，请帮助她规划一个开车的路线，使得按这个路线开车小明的疲劳度最小。
小芳将可能的道路分为大道和小道。大道比较好走，每走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号路口是连通的。
接下来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
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。
对于另外20%的评测用例，不存在小道；
对于另外20%的评测用例，所有的小道不相交；
对于所有评测用例，1 ≤ n ≤ 500，1 ≤ m ≤ 105，1 ≤ a, b ≤ n，t是0或1，c ≤ 105。保证答案不超过106。
比赛的时候用的dfs只骗了20分，因为复杂度2^500次方阿，正解是用dijkstra，因为有大路小路之分，所以要单独一个数组记录小路连续走了多长。注意用long long
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 struct node 5 { 6 LL to, w, type; 7 }; 8 vector<node>V[505]; 9 bool vis[505]; 10 LL dis[505], xl[505], n; 11 void dij(LL s) 12 { 13 LL i, j, k; 14 for(i = 1; i <= n; i++) 15 { 16 vis[i] = 0; 17 xl[i] = 0; 18 dis[i] = 1e9; 19 } 20 dis[1] = 0; 21 for(j = 1; j < n; j++) 22 { 23 LL min1 = 1e9; 24 for(i = 1; i <= n; i++) 25 { 26 if(min1 >= dis[i] && !vis[i]) 27 { 28 min1 = dis[i]; 29 k = i; 30 } 31 } 32 vis[k] = 1; 33 for(i = 0; i < V[k].size(); i++) 34 { 35 36 LL v = V[k][i].to, len = V[k][i].w, t = V[k][i].type; 37 if(vis[v]) continue; 38 if(t == 0) 39 { 40 if(dis[v] > dis[k] + len) 41 { 42 dis[v] = dis[k] + len; 43 xl[v] = 0; 44 } 45 } 46 else 47 { 48 if(!xl[k]) 49 { 50 if(dis[v] > dis[k] + len * len) 51 { 52 dis[v] = dis[k] + len * len; 53 xl[v] = len; 54 } 55 } 56 else 57 { 58 LL len1 = (xl[k] + len) * (xl[k] + len) - xl[k] * xl[k]; 59 if(dis[v] > dis[k] + len1) 60 { 61 dis[v] = dis[k] + len1; 62 xl[v] = xl[k] + len; 63 } 64 } 65 } 66 } 67 } 68 } 69 int main() 70 { 71 LL m, a, b; 72 node q; 73 scanf("%lld%lld", &n, &m); 74 while(m--) 75 { 76 scanf("%lld%lld%lld%lld", &q.type, &a, &b, &q.w); 77 q.to = b; 78 V[a].push_back(q); 79 q.to = a; 80 V[b].push_back(q); 81 } 82 dij(1); 83 printf("%lld\n", dis[n]); 84 return 0; 85 }