问题描述
小明和小芳出去乡村玩，小明负责开车，小芳来导航。
小芳将可能的道路分为大道和小道。大道比较好走，每走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 ≤ 10^5，1 ≤ a, b ≤ n，t是0或1，c ≤ 10^5。保证答案不超过10^6。
考试的时候$C$题花了太多时间，加上这题一开始想的方法不太好转移，$debug$到考试结束都没过样例。
然后回去重新写了一遍就过了，很可惜$C$题也没满分，$D$题还$0$分，还不如人家暴力还有十几二十分呢。
原来的代码只能过官方数据，但是实际上是存在错误的，修改之处参考了博客 _zlWang 。
这题很明显的多维最短路问题，用$dp[i][k]$表示当前走到了点$i$，以$k$的方式走过来的，$k=0$时表示从大路走过来，$k=1$时表示从小路走过来，但是这里有个问题，要保证小路-小路的边是当前最短的边，因此先把小路边单独拿出来做一遍$floyed$预处理，然后再把小路的各个点对间的最短距离当作边加入图中，再跑$SPFA$
疲劳度在小路-小路转移的时候为连续走小路的距离平方，因此入队节点最好记录三个信息：
${当前点u,转移方式f}$
然后就用$SPFA$进行转移，显然转移方程有四种：
最后$min(dp[n][0],dp[n][1])$就是答案。
这里有几组数据
5 6
0 1 2 30
0 2 4 30
1 1 4 4
0 1 3 17
1 3 4 1
1 4 5 10
答案：138
5 5
0 1 2 30
0 1 3 10
1 2 4 9
1 3 4 10
1 4 5 1
答案：130
4 5
1 1 2 2
0 1 2 10
0 1 3 5
0 3 2 4
1 2 4 3
答案：18
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 505;
const int M = 1e5 + 5;
struct edge
{
int to, nxt, f;
LL w;
edge() {}
edge(int _to, int _nxt, LL _w, int _f): to(_to), nxt(_nxt), w(_w), f(_f) {}
} E[M << 3];
struct info
{
int u, f;
};
int head[N], tot;
int vis[N][2];
LL d[N][2], G[N][N], inf = 0x3f3f3f3f3f3f3f3f;
void init()
{
CLR(head, -1);
}
inline void add(int s, int t, int w, int f)
{
E[tot] = edge(t, head[s], w, f);
head[s] = tot++;
}
inline LL sqr(const LL &x)
{
return x * x;
}
void spfa(int s)
{
queue<pii>Q;
Q.push(pii(s, 0));
Q.push(pii(s, 1));
vis[s][0] = 1;
vis[s][1] = 1;
d[s][0] = 0LL;
d[s][1] = 0LL;
while (!Q.empty())
{
pii t = Q.front();
Q.pop();
vis[t.fi][t.se] = 0;
for (int i = head[t.fi]; ~i; i = E[i].nxt)
{
int v = E[i].to;
if (E[i].f == 0) //走大路
{
if (t.se == 0) //从大路来
{
if (d[v][0] > d[t.fi][0] + E[i].w)
{
d[v][0] = d[t.fi][0] + E[i].w;
if (!vis[v][0])
{
vis[v][0] = 1;
Q.push(pii(v, 0));
}
}
}
else if (t.se == 1) //从小路来
{
if (d[v][0] > d[t.fi][1] + E[i].w)
{
d[v][0] = d[t.fi][1] + E[i].w;
if (!vis[v][0])
{
vis[v][0] = 1;
Q.push(pii(v, 0));
}
}
}
}
else//走小路
{
if (t.se == 0)//从大路来
{
if (d[v][1] > d[t.fi][0] + sqr(E[i].w))
{
d[v][1] = d[t.fi][0] + sqr(E[i].w);
if (!vis[v][1])
{
vis[v][1] = 1;
Q.push(pii(v, 1));
}
}
}
}
}
}
}
int main(void)
{
register int n, m, a, b, f, i, j, k;
register LL w;
while (~scanf("%d%d", &n, &m))
{
init();
for (i = 0; i <= n; ++i)
{
d[i][0] = d[i][1] = inf;
for (j = 0; j <= n; ++j)
G[i][j] = inf;
}
for (i = 0; i < m; ++i)
{
scanf("%d%d%d%lld", &f, &a, &b, &w);
if (f == 0)
{
add(a, b, w, f);
add(b, a, w, f);
}
else
{
G[a][b] = min(G[a][b], w);
G[b][a] = min(G[b][a], w);
}
}
for (k = 1; k <= n; ++k)
{
for (i = 1; i <= n; ++i)
{
for (j = i + 1; j <= n; ++j)
{
if (k == i || k == j)
continue;
if (G[i][j] > G[i][k] + G[k][j])
G[i][j] = G[j][i] = G[i][k] + G[k][j];
}
}
}
for (i = 1; i <= n; ++i)
{
for (j = i + 1; j <= n; ++j)
{
if (G[i][j] == inf)
continue;
add(i, j, G[i][j], 1);
add(j, i, G[i][j], 1);
}
}
spfa(1);
printf("%lld\n", min(d[n][0], d[n][1]));
}
return 0;
}