厦门制作公司网站,安卓原生app开发工具,网站建设做一个要多久,标准物质网站建设模板传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
每次连接[a,b][a,b][a,b]与[c,d][c,d][c,d]之间所有点#xff0c;让后跑最短路。
思路#xff1a;
比普通的优化建图能简单点#xff0c;我们只需要加两个虚点之间边权为111#xff0c;让后让某个点连…传送门
文章目录题意思路题意
每次连接[a,b][a,b][a,b]与[c,d][c,d][c,d]之间所有点让后跑最短路。
思路
比普通的优化建图能简单点我们只需要加两个虚点之间边权为111让后让某个点连接一个区间另一个连接另一个区间即可。注意是双向边所以区间交换一下再连一次就好啦。 最后求最短路的时候由于边权只有0,10,10,1所以用01bfs01bfs01bfs即可。 注意答案是每行一个CPeditorCP editorCPeditor用多了都不会自己看了。 复杂度O(nlogn)O(nlogn)O(nlogn)。
//#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 pairint,int PII;const int N500000*10,MN*2,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m,s,base;
int e[M],ne[M],w[M],h[N],idx;
int dis[N],leaf[N],tot;
bool st[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*2base,ubase,0); add(u*21base,ubase,0);build(u1,l,mid); build(u1|1,mid1,r);
}void change(int u,int l,int r,int ql,int qr,int st,int w,int op) {if(qllqrr) {if(!op) add(st,u,0);else add(u4*n,st,0);return;}int mid(lr)1;if(qlmid) change(u1,l,mid,ql,qr,st,w,op);if(qrmid) change(u1|1,mid1,r,ql,qr,st,w,op);
}void bfs() {dequeintq; q.push_front(leaf[s]);memset(dis,0x3f,sizeof(dis));dis[leaf[s]]0;while(q.size()) {int uq.front(); q.pop_front();for(int ih[u];~i;ine[i]) {int je[i];if(dis[j]dis[u]w[i]) {dis[j]dis[u]w[i];if(w[i]) q.push_back(j);else q.push_front(j);}}}for(int i1;in;i) printf(%d\n,dis[leaf[i]]);
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);memset(h,-1,sizeof(h));scanf(%d%d%d,n,m,s);basen*4; tot8*n1;build(1,1,n); for(int i1;in;i) add(leaf[i],leaf[i]base,0),add(leaf[i]base,leaf[i],0);for(int i1;im;i) {int a,b,c,d; scanf(%d%d%d%d,a,b,c,d);change(1,1,n,a,b,tot,1,0);change(1,1,n,c,d,tot1,1,1);add(tot1,tot,1); tot2;change(1,1,n,c,d,tot,1,0);change(1,1,n,a,b,tot1,1,1);add(tot1,tot,1); tot2;}bfs();return 0;
}
/**/
