P1629 邮递员送信（正反向建图 or 暴力）

题目链接

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