CCF 201712-4 行车路线 （spfa）

CCF 201712-4 行车路线 （spfa）

问题描述

小明和小芳出去乡村玩，小明负责开车，小芳来导航。小芳将可能的道路分为大道和小道。大道比较好走，每走 1 公里小明会增加 1 的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走 s 公里小明会增加 s^2 的疲劳度。例如：有 5 个路口，1 号路口到 2 号路口为小道，2 号路口到 3 号路口为小道，3 号路口到 4 号路口为大道，4 号路口到 5 号路口为小道，相邻路口之间的距离都是 2 公里。如果小明从 1 号路口到 5 号路口，则总疲劳值为 (2+2)^2+2+2^2=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 71 1 2 31 2 3 20 1 3 300 3 4 200 4 5 301 3 5 61 5 6 1

样例输出

76

思路

对于同一个点，假设最后一次从大道走过来和从小道走过来的花费是一样的，显然大道比较划算，因为它对下一次走小道的消耗没有贡献，从而可以保证最优解。

那么，我们把大道和小道分开计算。

首先通过 Floyd 算法合并一下所有的小道，然后再通过 spfa 寻找最优解。

每一次的迭代中我们只需要考虑当前状态的转移即可：[大道/小道 -> 大道]、[大道 -> 小道]

AC 代码

#include#define IO ios::sync_with_stdio(false);\ cin.tie(0);\ cout.tie(0);#define inf 0x3f3f3fusing namespace std;typedef long long LL;const int maxn = 5e2+10;int n,m;LL G[maxn][maxn];LL G2[maxn][maxn];LL dist[maxn];LL dist2[maxn];bool vis[maxn];void floyd(){ for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++) for(int k=1; k<=n; k++) G2[i][j] = min(G2[i][j],G2[i][k]+G2[k][j]);}void init(){ memset(dist,inf,sizeof(dist)); memset(dist2,inf,sizeof(dist2)); memset(vis,false,sizeof(vis)); memset(G,inf,sizeof(G)); memset(G2,inf,sizeof(G2));}void spfa(int st,int ed){ queue sk; dist[st] = dist2[st] = 0; vis[st] = true; sk.push(st); while(!sk.empty()) { int u = sk.front(); sk.pop(); vis[u] = false; for(int i=1; i<=n; i++) { int xlen = min(dist[u],dist2[u]); bool flag = false; if(dist[i] > xlen + G[u][i]) { dist[i] = xlen + G[u][i]; flag = true; } if(G2[u][i]!=4557430888798830399LL) { if(dist2[i] > dist[u] + G2[u][i] * G2[u][i]) { dist2[i] = dist[u] + G2[u][i] * G2[u][i]; flag = true; } } if(flag && !vis[i]) { vis[i] = true; sk.push(i); } } }}int main(){ IO; init(); cin>>n>>m; for (int i = 0; i < m ; i++) { LL t,a,b,c; cin>>t>>a>>b>>c; if(t) G2[a][b] = G2[b][a] = min(G2[a][b],c); else G[a][b] = G[b][a] = min(G[a][b],c); } floyd(); spfa(1,n); cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。