网站解析 cname,网络设置网址,网站锚文本与标签,青岛北京网站建设公司问题描述#xff1a; 小明和小芳出去乡村玩#xff0c;小明负责开车#xff0c;小芳来导航。小芳将可能的道路分为大道和小道。大道比较好走#xff0c;每走1公里小明会增加1的疲劳度。小道不好走#xff0c;如果连续走小道#xff0c;小明的疲劳值会快速增加#xff0c…问题描述 小明和小芳出去乡村玩小明负责开车小芳来导航。小芳将可能的道路分为大道和小道。大道比较好走每走1公里小明会增加1的疲劳度。小道不好走如果连续走小道小明的疲劳值会快速增加连续走s公里小明会增加s*s的疲劳度。例如有5个路口1号路口到2号路口为小道2号路口到3号路口为小道3号路口到4号路口为大道4号路口到5号路口为小道相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口则总疲劳值为(22)2222162422。现在小芳拿到了地图请帮助她规划一个开车的路线使得按这个路线开车小明的疲劳度最小。 输入格式输入的第一行包含两个整数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疲劳度为5225然后从3走大道经过4到达5疲劳度为203050最后从5走小道到6疲劳度为1。总共为76。数据规模和约定 对于30%的评测用例1 ≤ n ≤ 81 ≤ m ≤ 10对于另外20%的评测用例不存在小道对于另外20%的评测用例所有的小道不相交对于所有评测用例1 ≤ n ≤ 5001 ≤ m ≤ 1e51 ≤ a, b ≤ nt是0或1c ≤ 105。保证答案不超过1e6。分析 典型的最短路问题容易想到如果没有小路那么这题就是最基础的最短路直接用dijkstra求解可以通过60%的数据题目中并没有说明是否存在重边 10%的数据小路增加的疲劳度计算是连续走小路的路长的平方因此在多段图中就不能像简单的最短路问题一样直接存储节点的编号和到这个点的最短路径长度根据题目描述在dijkstra的过程中每个节点都记录 到该节点的前一段走小路的长度s、走小路前的疲劳值、走到这点的总疲劳值设置从节点1到节点i的最小疲劳值为dist1[i] - 最后一段是大路dist2[i] - 最后一段是小路根据当前节点到下一节点路径类别计算产生的总疲劳值根据情况入队优先队列实现的dijkstra注意c1e5, 计算过程中可能会出现 c*c 这种计算使用int会爆int 把整型全部设为long long 20%的数据别问我为什么知道那些百分比说出来都是泪
#include bits/stdc.h
using namespace std;
typedef long long LL;
const LL INF 1e910;
const LL maxn 505;
typedef pairLL,LL P;vectorPmp[maxn][maxn];
LL dist1[maxn],dist2[maxn],vis1[maxn],vis2[maxn];
LL n,m,t,a,b,c;
struct node
{LL id,totCost,daCost,xiaoCost,s;node(){}node(LL a,LL b,LL c) {ida;totCostb;sc;}node(LL a,LL b,LL c,LL d){ida;totCostb;sc;daCost d;}friend bool operator(const node a,const node b){if(a.totCost!b.totCost)return a.totCostb.totCost;return a.sb.s;}
};priority_queuenodepriq;void init()
{while(!priq.empty()) priq.pop();for(LL i0;imaxn;i){dist1[i] dist2[i] INF;vis1[i] vis2[i] 0;}for(LL i0;imaxn;i)for(LL j0;jmaxn;j)mp[i][j].clear();}void input()
{cinnm;while(m--){cintabc;mp[a][b].push_back(P(t,c));mp[b][a].push_back(P(t,c));}
}void dijkstra()
{dist1[1] dist2[1] 0;vis2[1]1;priq.push(node(1,0,0,0));while(!priq.empty()){node e priq.top();priq.pop();LL nowe.id;LL totCost e.totCost;LL daCost e.daCost;LL s e.s;if(s) vis2[now]1;else vis1[now]1;for(LL i2;in;i){if(vis1[i]vis2[i]) continue;for(LL j0;jmp[now][i].size();j){P xxx mp[now][i][j];if(xxx.first){ // 这条路是小路LL len sxxx.second;LL cost daCost len*len; ///watch out!! len*lenintif(costdist2[i]) {dist2[i] cost;priq.push(node(i,cost,len,daCost));}}else { // 这条路是大路LL cost totCost xxx.second;if(costdist1[i]){dist1[i] cost;priq.push(node(i,cost,0,cost));}}}}}
}int main()
{init();input();dijkstra();coutmin(dist1[n],dist2[n])endl;return 0;
}转载于:https://www.cnblogs.com/star-and-me/p/9623828.html
