题目链接
https://www.luogu.com.cn/problem/P1629
思路和农场派对这题一样,我们需要正反向建图,然后跑迪杰斯特拉然后再分别加上
[
2
,
n
]
[2,n]
[2,n]的dis
值(因为题目中保证了每个点可达),但是这道题可以直接对每个点跑迪杰斯特拉然后再吸一点氧暴力跑过去
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
const int N=2e6+5;//数据范围
struct edge{//存储边
int u,v,w,next;//u为起点,v为终点,w为权值,next为前继
};
edge e[N];
int head[N],dis[N],n,m,s,cnt;//head为链中最上面的,dis表示当前答案,n为点数,m为边数,s为起点,cnt记录当前边的数量
bool vis[N];//vis表示这个点有没有走过
struct node{
int w,to;//w表示累加的权值,to表示到的地方
bool operator dis[u]+e[i].w){//若中转后更优,就转
dis[v]=dis[u]+e[i].w;//更新
q.push(node{dis[v],v});//压入队列
}
}
}
}
int U[N],V[N],W[N];
void init(){
int l = max(n,m);
for(int i = 1;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?