SPFA+寻路(行路难,洛谷2832)

时间:2022-09-23 18:14:29

注意:本博客代码被黑心数据Hack,有空补回来

啊啊啊这道难题总算是做出来了,首先是帅比浮云的题解发出来一下:http://www.cnblogs.com/fuyun-boy/p/5922742.html

原题目地址:https://www.luogu.org/problem/show?pid=2832

题目背景

小X来到了山区,领略山林之乐。在他乐以忘忧之时,他突然发现,开学迫在眉睫

题目描述

山区有n座山。山之间有m条羊肠小道,每条连接两座山,只能单向通过,并会耗费小X一定时间。

小X现在在1号山,他的目的是n号山,因为那里有火车站。

然而小X的体力是有限的。他每通过一条羊肠小道,就会变得更疲劳,导致他通过任意一条羊肠小道的时间都增加1。

输入输出格式

输入格式:

第一行两个数,n,m

第2行到第m+1行,每行3个数A,B,C,表示A、B之间有一条羊肠小道,可以让小X花费C的时间从A移动到B

输出格式:

两行
第一行一个数T,表示小X需要的最短时间

第二行若干个数,用空格隔开,表示小X的移动路线

例:1 4 2 5表示:小X从1号山开始,移动到4号山,再到2号山,最后到5号山。

输入输出样例

输入样例#1:
5 8
2 4 2
5 2 1
1 2 1
4 3 2
1 3 3
4 5 2
1 5 8
3 5 3
输出样例#1:
7
1 3 5

说明

n<=10000, m<=200000

数据保证没有多条最短路径

【题解】

这道题就是最短路的变体,不过从起点到终点每多走一条边就要多加一点权值。

比如说原来的权值是6+7+9+3+5,之后的权值就是6+(7+1)+(9+2)+(3+3)+(5+4)了。

下面的这个是我写的代码。我的解决方法就是加上两个数组,一个是r,一个是tr。

d数组还是spfa一如既往的d数组,是除去这道题额外的条件的数组。

tr数组是补充数组(废话),d[i]+tr[i]表示从起点走到这个点的最小花费。

r[i]是按照从起点走到第i个节点花费d[i]+tr[i]的最短路径时,最后一次的增加值。

比如说上面的那个6+(7+1)+(9+2)+(3+3)+(5+4),表示一条路径,则这条路径终点节点的r数组的值是4。

因为走到这里最后一次加上的数字是4。

pre数组不说了,帅比浮云说了很清楚。。。

#include <cstdio>
#include <cstring>
#include <queue>
#define mp make_pair
using namespace std;
int n,m,h;
struct edge
{
int v,w;
edge*next;
};
edge* link[10001];
int d[10001],r[10001],tr[10001],pre[10001];
bool v[10001];
void add(int u,int v,int w)
{
edge* p=new edge;
p->v=v;
p->w=w;
p->next=link[u];
link[u]=p;
}
void del(edge* p)
{
if(p!=NULL)
{
del(p->next);
delete p;
}
}
void spfa()
{
queue<int>q;
memset(d,0x3f,sizeof(d));
d[1]=0;
q.push(1);
v[1]=true;
while(!q.empty())
{
int x=q.front();
q.pop();
v[x]=false;
for(edge* p=link[x];p!=0;p=p->next)
{
if(d[x]+tr[x]+p->w+r[x]<d[p->v]+tr[p->v])
{
d[p->v]=d[x]+p->w;
tr[p->v]=tr[x]+r[x];
r[p->v]=r[x]+1;
pre[p->v]=x;
if(v[p->v]==false)
{
v[p->v]=true;
q.push(p->v);
}
}
}
}
}
void print(int n)
{
if(n!=1)
print(pre[n]);
printf("%d ",n);
}
int main()
{
int CO2,H2O,H2CO3;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&CO2,&H2O,&H2CO3);
add(CO2,H2O,H2CO3);
}
spfa();
printf("%d\n",d[n]+tr[n]);
print(n);
for(int i=1;i<=n;i++)
del(link[i]);
return 0;
}

祝各位NOIP2016 RP++ SCORE++

SPFA+寻路(行路难,洛谷2832)的更多相关文章

  1. spfa模板(洛谷3371)

    洛谷P3371 //spfa:求s到各点的最短路,可含负权边 #include <cstdio> using namespace std; ,max_m=,inf=; struct ety ...

  2. 【模板】负环(SPFA&sol;Bellman-Ford)&sol;洛谷P3385

    题目链接 https://www.luogu.com.cn/problem/P3385 题目大意 给定一个 \(n\) 个点有向点权图,求是否存在从 \(1\) 点出发能到达的负环. 题目解析 \(S ...

  3. 洛谷P2832 行路难 分析&plus;题解代码【玄学最短路】

    洛谷P2832 行路难 分析+题解代码[玄学最短路] 题目背景: 小X来到了山区,领略山林之乐.在他乐以忘忧之时,他突然发现,开学迫在眉睫 题目描述: 山区有n座山.山之间有m条羊肠小道,每条连接两座 ...

  4. NOIP2017提高组Day1T3 逛公园 洛谷P3953 Tarjan 强连通缩点 SPFA 动态规划 最短路 拓扑序

    原文链接https://www.cnblogs.com/zhouzhendong/p/9258043.html 题目传送门 - 洛谷P3953 题目传送门 - Vijos P2030 题意 给定一个有 ...

  5. 洛谷P1342 请柬(SPFA)

    To 洛谷.1342 请柬 题目描述 在电视时代,没有多少人观看戏剧表演.Malidinesia古董喜剧演员意识到这一事实,他们想宣传剧院,尤其是古色古香的喜剧片.他们已经打印请帖和所有必要的信息和计 ...

  6. 洛谷P1144 最短路计数(SPFA)

    To 洛谷.1144 最短路计数 题目描述 给出一个N个顶点M条边的无向无权图,顶点编号为1-N.问从顶点1开始,到其他每个点的最短路有几条. 输入输出格式 输入格式: 输入第一行包含2个正整数N,M ...

  7. 洛谷&period;4015&period;运输问题&lpar;SPFA费用流&rpar;

    题目链接 嗯..水题 洛谷这网络流二十四题的难度评价真神奇.. #include <queue> #include <cstdio> #include <cctype&g ...

  8. 【题解】洛谷P1073 &lbrack;NOIP2009TG&rsqb; 最优贸易(SPFA&plus;分层图)

    次元传送门:洛谷P1073 思路 一开始看题目嗅出了强连通分量的气息 但是嫌长没打 听机房做过的dalao说可以用分层图 从来没用过 就参考题解了解一下 因为每个城市可以走好几次 所以说我们可以在图上 ...

  9. 洛谷P1186 玛丽卡 spfa&plus;删边

    洛谷P1186 玛丽卡http://blog.csdn.net/huihao123456/article/details/73414139题目描述 麦克找了个新女朋友,玛丽卡对他非常恼火并伺机报复. ...

随机推荐

  1. OC初步 (一)

    OC完全兼容C, 代码后缀名一般习惯用 *.m 或 *.mm,按惯例从 "Hello,World!" 开始,我们编写一个 test.mm 文件如下: #import <Fou ...

  2. CSS书写规范、命名规范、网易CSS框架NEC

    网易CSS框架NEC:http://nec.netease.com/ NEC框架的CSS规范:  CSS规范 - 分类方法 CSS规范 - 命名规则 CSS规范 - 代码格式 CSS规范 - 优化方案 ...

  3. java中Jbutton常用设置

    . 对JButton大小的设置     ——因为JButen是属于小器件类型的,所以一般的setSize不能对其惊醒大小的设置,所以一般我们用     button.setPreferredSize( ...

  4. css3动画在动作结束时保持该状态不变的解决办法

    animation-fill-mode : none | forwards | backwards | both; none:不改变默认行为. forwards :当动画完成后,保持最后一个属性值(在 ...

  5. &lbrack;moka同学摘录&rsqb;Yii2 csv数据导出扩展

    yii2-thecsv(Yii2框架csv数据导出扩展) github: https://github.com/13552277443/yii2-thecsv 1.安装 运行 php composer ...

  6. 【jdbcTemplate】使用jdbcTemplate查询的三种回调

    用于查询的回调接口定义主要有以下三种: org.springframework.jdbc.core.ResultSetExtractor.  基本上属于JdbcTemplate内部使用的Callbac ...

  7. JavaScript笔记之第五天

    JavaScript 对象 JavaScript 中的所有事物都是对象:字符串.数值.数组.函数... 此外,JavaScript 允许自定义对象. 所有事物都是对象 JavaScript 提供多个内 ...

  8. cocos2dx 屏幕分辨率

    http://cn.cocos2d-x.org/article/index?type=cocos2d-x&url=/doc/cocos-docs-master/manual/framework ...

  9. android基础----&gt&semi;发送和接收短信

    收发短信应该是每个手机最基本的功能之一了,即使是许多年前的老手机也都会具备这项功能,而Android 作为出色的智能手机操作系统,自然也少不了在这方面的支持.今天我们开始自己创建一个简单的发送和接收短 ...

  10. &lbrack;TEST123&rsqb; Performance Test

    https://blog.csdn.net/zhouping19851013/article/details/82870789 https://www.cnblogs.com/jackei/archi ...