唐山建设集团下岗职工网站,销帮帮crm,python做网站框架,网页开发定制传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
实现如下连边后跑最短路。
思路#xff1a;
优化建图板子题#xff0c;优化思路就是将区间分割成若干个线段树上的线段#xff0c;与线段树分治有点类似#xff0c;由于有点向区间也有区间向点的边思路题意
实现如下连边后跑最短路。
思路
优化建图板子题优化思路就是将区间分割成若干个线段树上的线段与线段树分治有点类似由于有点向区间也有区间向点的边那么我们需要建两颗线段树点向区间的树是自顶向下连边区间向点的是自底向上连边最后两棵树的最后一层需要与原来的nnn个点连双向(未经说明都是单向边)比如下面这个图(盗用了日报的图) 让后我们就按照图来建边就好啦我这里第一颗编号是[1,4∗n][1,4*n][1,4∗n]第二棵编号是[4∗n1,8∗n][4*n1,8*n][4∗n1,8∗n]绿色点是[8∗n1,9∗n][8*n1,9*n][8∗n1,9∗n]。 当然可以舍去绿色的点直接以线段树叶子节点为绿色的点下面也给出代码了只需要记一下leaf[i]leaf[i]leaf[i]即可。
// Problem: B. Legacy
// Contest: Codeforces - Codeforces Round #406 (Div. 1)
// URL: https://codeforces.com/problemset/problem/786/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairLL,int PII;const int N900200,MN*40,mod1e97,INF0x3f3f3f3f;
const LL inf0x3f3f3f3f3f3f3f3f;
const double eps1e-6;int n,q,s,b1,b2;
int e[M],ne[M],w[M],h[N],idx;
LL dis[N];
bool st[N];
//第一颗线段树1-4*n 第二棵4*n1-8*n 点8*n1-9*nvoid add(int a,int b,int c) {e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;
}void build(int u,int l,int r) {if(lr) {add(u,l8*n,0); add(l8*n,u,0);add(u4*n,l8*n,0); add(l8*n,u4*n,0);return;}add(u,u*2,0); add(u,u*21,0);add(u*24*n,u4*n,0); add(u*214*n,u4*n,0);int mid(lr)1;build(u1,l,mid); build(u1|1,mid1,r);
}void change1(int u,int l,int r,int ql,int qr,int st,int cs) {if(qllqrr) {add(st8*n,u,cs);return;}int mid(lr)1;if(qlmid) change1(u1,l,mid,ql,qr,st,cs);if(qrmid) change1(u1|1,mid1,r,ql,qr,st,cs);
}void change2(int u,int l,int r,int ql,int qr,int st,int cs) {if(qllqrr) {add(u4*n,st8*n,cs);return;}int mid(lr)1;if(qlmid) change2(u1,l,mid,ql,qr,st,cs);if(qrmid) change2(u1|1,mid1,r,ql,qr,st,cs);
}void dijkstra() {priority_queuePII,vectorPII,greaterPII q; q.push({0ll,s8*n});memset(dis,0x3f3f3f3f,sizeof(dis));dis[s8*n]0;while(q.size()) {PII uq.top(); q.pop();if(st[u.Y]) continue;st[u.Y]1;for(int ih[u.Y];~i;ine[i]) {int je[i];if(dis[j]dis[u.Y]w[i]) {dis[j]dis[u.Y]w[i];q.push({dis[j],j});}}}for(int i1;in;i) printf(%lld ,dis[i8*n]inf? -1:dis[i8*n]);
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);memset(h,-1,sizeof(h));cinnqs;build(1,1,n);while(q--) {int op,v,l,r,c;scanf(%d,op);if(op1) {scanf(%d%d%d,l,r,c);add(l8*n,r8*n,c);}else if(op2) {scanf(%d%d%d%d,v,l,r,c);change1(1,1,n,l,r,v,c);}else {scanf(%d%d%d%d,v,l,r,c);change2(1,1,n,l,r,v,c);}}dijkstra();return 0;
}
/**/
// Problem: B. Legacy
// Contest: Codeforces - Codeforces Round #406 (Div. 1)
// URL: https://codeforces.com/problemset/problem/786/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairLL,int PII;const int N800200,MN*20,mod1e97,INF0x3f3f3f3f;
const LL inf0x3f3f3f3f3f3f3f3f;
const double eps1e-6;int n,q,s,b1,b2;
int e[M],ne[M],w[M],h[N],idx;
int leaf[N];
LL dis[N];
bool st[N];
//第一颗线段树1-4*n 第二棵4*n1-8*n void add(int a,int b,int c) {e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;
}void build(int u,int l,int r) {if(lr) {leaf[l]u;return;}int mid(lr)1;add(u,u*2,0); add(u,u*21,0);add(u*24*n,u4*n,0); add(u*214*n,u4*n,0);build(u1,l,mid); build(u1|1,mid1,r);
}void change1(int u,int l,int r,int ql,int qr,int st,int w) {if(qllqrr) {add(st,u,w);return;}int mid(lr)1;if(qlmid) change1(u1,l,mid,ql,qr,st,w);if(qrmid) change1(u1|1,mid1,r,ql,qr,st,w);
}void change2(int u,int l,int r,int ql,int qr,int st,int w) {if(qllqrr) {add(u4*n,st,w);return;}int mid(lr)1;if(qlmid) change2(u1,l,mid,ql,qr,st,w);if(qrmid) change2(u1|1,mid1,r,ql,qr,st,w);
}void dijkstra() {memset(dis,0x3f3f3f3f,sizeof(dis));priority_queuePII,vectorPII,greaterPIIq;q.push({s,leaf[s]}); dis[leaf[s]]0;while(q.size()) {PII uq.top(); q.pop();if(st[u.Y]) continue;st[u.Y]1;for(int ih[u.Y];~i;ine[i]) {int je[i];if(dis[j]dis[u.Y]w[i]) {dis[j]dis[u.Y]w[i];q.push({dis[j],j});}}}for(int i1;in;i) printf(%lld ,dis[leaf[i]]inf? -1:dis[leaf[i]]);
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);memset(h,-1,sizeof(h));cinnqs;build(1,1,n);for(int i1;in;i) add(leaf[i],leaf[i]4*n,0),add(leaf[i]4*n,leaf[i],0);while(q--) {int op,v,l,r,c;scanf(%d,op);if(op1) {scanf(%d%d%d,l,r,c);add(leaf[l],leaf[r],c);}else if(op2) {scanf(%d%d%d%d,v,l,r,c);change1(1,1,n,l,r,leaf[v],c);}else {scanf(%d%d%d%d,v,l,r,c);change2(1,1,n,l,r,leaf[v],c);}}dijkstra();return 0;
}
/**/
