厦门自己建网站,新网站建设渠道,软件开发工程师是前端还是后端,流媒体 网站开发3255. 行车路线 小明和小芳出去乡村玩#xff0c;小明负责开车#xff0c;小芳来导航。 小芳将可能的道路分为大道和小道。 大道比较好走#xff0c;每走 1 公里小明会增加 1 的疲劳度。 小道不好走#xff0c;如果连续走小道#xff0c;小明的疲劳值会快速增加#xff0…3255. 行车路线 小明和小芳出去乡村玩小明负责开车小芳来导航。 小芳将可能的道路分为大道和小道。 大道比较好走每走 1 公里小明会增加 1 的疲劳度。 小道不好走如果连续走小道小明的疲劳值会快速增加连续走 s 公里小明会增加 s^2 的疲劳度。 例如有 5 个路口1 号路口到 2 号路口为小道2 号路口到 3 号路口为小道3 号路口到 4 号路口为大道4 号路口到 5 号路口为小道相邻路口之间的距离都是 2 公里。 如果小明从 1 号路口到 5 号路口则总疲劳值为 (22)^222^2162422。 现在小芳拿到了地图请帮助她规划一个开车的路线使得按这个路线开车小明的疲劳度最小。 输入格式 输入的第一行包含两个整数 n,m分别表示路口的数量和道路的数量。路口由 1 至 n 编号小明需要开车从 1 号路口到 n 号路口。 接下来 m 行描述道路每行包含四个整数 t,a,b,c表示一条类型为 t连接 a 与 b 两个路口长度为 c 公里的双向道路。其中 t 为 0 表示大道t 为 1 表示小道。 保证 1 号路口和 n 号路口是连通的。 输出格式 输出一个整数表示最优路线下小明的疲劳度。 数据范围 对于 30% 的评测用例1≤n≤81≤m≤10 对于另外 20% 的评测用例不存在小道 对于另外 20% 的评测用例所有的小道不相交 对于所有评测用例1≤n≤5001≤m≤10^51≤a,b≤nt 是 0 或 1c≤10^5。保证答案不超过 10^6。 输入样例 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疲劳度为 5^225然后从 3 走大道经过 4 到达 5疲劳度为 203050最后从 5 走小道到 6疲劳度为 1。 总共为 76。 因为保证答案不超过10^6, 所以连续小路长度超过1000 因为点的数据范围为500所以可以拆点第二维表示当前连续小路长度
#include bits/stdc.husing namespace std;const int N 510, M 200010, INF 1e6;int n, m;
int h[N], e[M], f[M], w[M], ne[M], idx; //f表示道路类型
int dist[N][1010];
bool st[N][1010];struct Node
{int x, y, v; //x当前点y当前连续小路长度v为dist[x][y]bool operator (const Node t) const{return v t.v; //小根堆从小到大}
};void add(int t, int a, int b, int c)
{e[idx] b, f[idx] t, w[idx] c, ne[idx] h[a], h[a] idx ;
}void dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1][0] 0;priority_queueNode heap;heap.push({1, 0, 0});while (heap.size()){Node t heap.top();heap.pop();if (st[t.x][t.y]) continue; //dijkstra()所有点只遍历一次st[t.x][t.y] true;for (int i h[t.x]; ~i; i ne[i]){int j e[i], y t.y;if (f[i]) //小路{y w[i]; //小路长度更新if (y 1000) //连续小路长度一定小于1000{if (dist[j][y] t.v - t.y * t.y y * y){dist[j][y] t.v - t.y * t.y y * y;if (dist[j][y] INF)heap.push({j, y, dist[j][y]});}}}else{if (dist[j][0] t.v w[i]){dist[j][0] t.v w[i];if (dist[j][0] INF)heap.push({j, 0, dist[j][0]});}}}}
}int main()
{cin n m;memset(h, -1, sizeof h);while (m --){int t, a, b, c;scanf(%d%d%d%d, t, a, b, c);add(t, a, b, c), add(t, b, a, c);}dijkstra();int res INF;for (int i 0; i 1000; i ) res min(res, dist[n][i]);//表示最后一段小路的长度为i的前提下1到n的最短距离cout res;return 0;
}
