361行代码的由来
数据分治大发好啊～
NOI的签到题，可怜我在家打了一下午才搞了80分。
正解应该是kruskal重构树或排序+可持久化并查集。
我就分点来讲暴力80分做法吧(毕竟正解我也没太懂)～
前6个点
这6个点有两种做法：
法1：最短路。
这6个点都是离线的，而且只有一种海拔，所以直接最短路。
跑完之后，直接判断海拔与水位，输出即可。
不过这些分也并不好拿，spfa会被卡，要用堆优化dijkstra。
法2：离线排序+并查集。
其实这个暴力思想就是正解思想了，很好想到的。
首先跑个最短路求一下1号点到所有点的距离，按照边权从大到小排序，对于询问也按照水位线从大到小排一下序。
显然，当一条边加入以后，就不可能再删除，因为水位线只会慢慢降低。
这样这个问题就可以转化成，当前询问下，如果把所有大于当前水位线的边加入图中，那么从起点出发，求它所能到达的点中与1号点距离最小的点即可。
加边时用并查集维护一下即可：
即对于两个点a，b在并查集中的祖先x，y，如果dis[x]>dis[y]，则令fa[x]=y。
这样并查集在查询时，就可以以常数的复杂度找到当前询问下的答案。注意加边是在一个查询开始前，将所有海拔大于水位线的边加进去。
树和链的5个点
这里我们可以考虑倍增。
预处理3个ST表：dpt[][]，num[][]，xiao[][]
分别表示从x点跳(2^j)步，从x到向上(2^j)个点的花费，最后是从x到向上(2^j)个点中海拔最小的点。
所以算法也很简单，先调到海拔最小的点，然后再倍增求花费。
当然也可以用之前讲的离线排序+并查集。
3个离线大点
直接按上面说的离线并查集即可。
15和16两个在线小点
离线并查集不管用了？别担心。
因为数据范围小，直接在线，每次询问用一个新的并查集维护。
反正能过。
超长代码菌～
请忽略代码中的正解部分，啦啦啦～
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,int> Pair;
void read(int &aa)
{
aa=0;char c=getchar();bool f=0;
while (c>'9'||c<'0') {if (c=='-') f=1;c=getchar();}
while (c>='0'&&c<='9')
aa=(aa<<3)+(aa<<1)+(c^48),c=getchar();
(f)&&(aa=-aa);
}
const int N=800020;
int n,m,q,k,s;
struct Edge {
int next,cost,high,to;
}e[N<<2];
int last[N],spfaflag;
void add(int x,int y,int c,int h)
{
e[++last[0]].to=y;
e[last[0]].cost=c;e[last[0]].next=last[x];
e[last[0]].high=h;last[x]=last[0];
}
int vis[N];
long long dis[N];
queue <int> Q;
priority_queue< Pair,vector<Pair>,greater<Pair> >que;
void spfa()
{
while (!Q.empty()) Q.pop();
for (int i=1;i<=n;++i) dis[i]=2e9+1;
memset(vis,0,sizeof(vis));
vis[1]=1;Q.push(1);dis[1]=0;
while (!Q.empty()) {
int x=Q.front();Q.pop();vis[x]=0;
for (int i=last[x];i;i=e[i].next) {
int y=e[i].to,c=e[i].cost;
if (dis[y]>dis[x]+c) {
dis[y]=dis[x]+c;
if (!vis[y]) vis[y]=1,Q.push(y);
}
}
}
}
void dijsktra()
{
while (!que.empty()) que.pop();
for (int i=1;i<=n;++i) dis[i]=2e9+1;
memset(vis,0,sizeof(vis));
dis[1]=0;
que.push(make_pair(dis[1],1));
while (!que.empty()) {
Pair now=que.top();que.pop();
if (vis[now.second]) continue;
vis[now.second]=1;
for (int i=last[now.second];i;i=e[i].next)
if (dis[now.second]+e[i].cost<dis[e[i].to]) {
dis[e[i].to]=dis[now.second]+e[i].cost;
if (!vis[e[i].to]) que.push(make_pair(dis[e[i].to],e[i].to));
}
}
}
int bian[N],gao[N];
void chain()
{
int ed,pp,chainflag;
long long ans,preans=0;
read(q);read(k);read(s);
for (int i=1;i<=q;++i) {
chainflag=ans=0;
read(ed);read(pp);
ed=(ed+k*preans-1)%n+1;
pp=(pp+k*preans)%(s+1);
for (int t=ed;t>1;--t)
if (chainflag||gao[t]<=pp)
ans+=bian[t],chainflag=1;
printf("%lld
",ans);
preans=ans;
}
}
int dep[N],dpt[N][33],xiao[N][33],num[N][33];
void dfs(int x,int d)
{
dep[x]=d;
for (int i=last[x];i;i=e[i].next) {
int y=e[i].to;
if (!dep[y]) {
dpt[y][0]=x;
xiao[y][0]=e[i].high;
num[y][0]=e[i].cost;
dfs(y,d+1);
}
}
}
void init()
{
for (int j=1;j<=24;++j)
for (int i=1;i<=n;++i) {
dpt[i][j]=dpt[dpt[i][j-1]][j-1];
xiao[i][j]=min(xiao[i][j-1],xiao[dpt[i][j-1]][j-1]);
num[i][j]=num[i][j-1]+num[dpt[i][j-1]][j-1];
}
}
int zuo(int x,int gaodu)
{
int ans=0;
for (int j=24;j>=0;--j) {
if (xiao[x][j]>gaodu&&dpt[x][j])
x=dpt[x][j];
}
if (x!=1) {
for (int j=24;j>=0;--j)
if (dpt[x][j])
ans+=num[x][j],x=dpt[x][j];
return ans;
}
return 0;
}
void tree()
{
int ed,pp;
dfs(1,1);init();
read(q);read(k);read(s);
int ans,preans=0;
for (int i=1;i<=q;++i) {
read(ed);read(pp);
ed=(ed+k*preans-1)%n+1;
pp=(pp+k*preans)%(s+1);ans=zuo(ed,pp);
printf("%d
",ans);preans=ans;
}
}
struct Line {
int from,to,cost,high;
}line[N<<1];
struct ask {
int shui,id,v,res;
}wen[N];
int baba[N];
bool pai1(ask t1,ask t2)
{
return t1.shui>t2.shui;
}
bool pai2(Line t1,Line t2)
{
return t1.high>t2.high;
}
bool pai3(ask t1,ask t2)
{
return t1.id<t2.id;
}
int find(int x)
{
return x!=baba[x]?baba[x]=find(baba[x]):x;
}
void unionset(int x,int y)
{
int u=find(x),v=find(y);
if (u==v) return;
if (dis[u]>dis[v]) baba[u]=v;
else baba[v]=u;
}
void outline()
{
for (int i=1;i<=q;++i) {
read(wen[i].v);read(wen[i].shui);
wen[i].id=i;
}
sort(&wen[1],&wen[1+q],pai1);
sort(&line[1],&line[1+m],pai2);
for (int i=1;i<=n;++i) baba[i]=i;
int now=1;
for (int i=1;i<=q;++i) {
while (now<=m&&line[now].high>wen[i].shui)
unionset(line[now].from,line[now].to),++now;
wen[i].res=dis[find(wen[i].v)];
}
sort(wen+1,wen+1+q,pai3);
for (int i=1;i<=q;++i) printf("%d
",wen[i].res);
}
void navi_inline()
{
int lastans=0,instead;
sort(line+1,line+1+m,pai2);
for (int j=1;j<=q;++j) {
for (int i=1;i<=n;++i) baba[i]=i;
int now=1;
read(instead);
int v=(instead+k*lastans-1)%n+1;
read(instead);
int p=(instead+k*lastans)%(s+1);
while (now<=m&&line[now].high>p)
unionset(line[now].from,line[now].to),++now;
lastans=dis[find(v)];
printf("%d
",lastans);
}
}
bool cmp(Line t1,Line t2)
{
return t1.high>t2.high;
}
Line line2[N<<1];
int fa[N],ceng[N],tiao[N][25];
struct eeee {
int to,next;
}ee[N<<1];
int head[N];
void jia(int x,int y)
{
ee[++head[0]].to=y;ee[head[0]].next=head[x];
head[x]=head[0];
}
void shensou(int x,int pa)
{
ceng[x]=ceng[pa]+1,tiao[x][0]=pa;
for (int i=1;i<=24;++i)
tiao[x][i]=tiao[tiao[x][i-1]][i-1];
for (int i=head[x];i;i=ee[i].next) {
int y=ee[i].to;
shensou(y,x);
line2[x].cost=min(line2[x].cost,line2[y].cost);
}
}
int xunwenta(int x,int y)
{
for (int i=24;i>=0;--i)
if (ceng[x]-(1<<i)>0&&line2[tiao[x][i]].high>y)
x=tiao[x][i];
return line2[x].cost;
}
int find2(int x)
{
return x==fa[x]?x:fa[x]=find2(fa[x]);
}
void zhengjie_wo_wu_di_la_hahaha_kruskal()
{
int tott=0,cntt=n;
for (int i=1;i<=(n<<1);++i) fa[i]=i;
sort(line+1,line+m+1,cmp);
for (int i=1;i<=m;++i) {
int u=line[i].from,v=line[i].to;
int fx=find2(u),fy=find2(v);
if (fx!=fy) {
jia(++cntt,fx);
jia(cntt,fy);
fa[fx]=cntt;
fa[fy]=cntt;
line2[cntt].high=line[i].high;
++tott;
}
if (tott+1==n) break;
}
int lastans=0;
shensou(cntt,0);
int tttt;
while (q--) {
read(tttt);
int x=(k*lastans+tttt-1)%n+1;
read(tttt);
int y=(k*lastans+tttt)%(s+1);
printf("%d
",lastans=xunwenta(x,y));
}
}
int main()
{
int T,x,y,c,h;read(T);
while (T--) {
memset(last,0,sizeof(last));
memset(gao,0,sizeof(gao));
memset(bian,0,sizeof(bian));
memset(dep,0,sizeof(dep));
memset(dpt,0,sizeof(dpt));
memset(xiao,0,sizeof(xiao));
memset(num,0,sizeof(num));
memset(head,0,sizeof(head));
memset(tiao,0,sizeof(tiao));
read(n);read(m);bool flag=1;
int pre=0,mp=2;
for (int i=1;i<=m;++i) {
read(x);read(y);read(c);read(h);
gao[y]=h;bian[y]=c;
if (x+1!=y) flag=0;
if (pre!=h) --mp,pre=h;
add(x,y,c,h);add(y,x,c,h);
line[i].from=x;line[i].to=y;
line[i].cost=c;line[i].high=h;
}
if (mp==1) {
int ed,pp;
read(q);read(k);read(s);dijsktra();
for (int i=1;i<=q;++i) {
spfaflag=0;
read(ed);read(pp);
ed=(ed-1)%n+1;pp=pp%(s+1);
if (pp>=pre) spfaflag=1;
printf("%lld
",!spfaflag?dis[1]:dis[ed]);
}
continue;
}
if (m+1==n) {
if (flag) chain();
else tree();
continue;
}
read(q);read(k);read(s);
if (!k) {
dijsktra();
outline();
continue;
}
if (k&&n<=1500) {
dijsktra();
navi_inline();
continue;
}
for (int i=n+1;i<=(n<<1);++i)
line2[i].cost=0x3f3f3f3f;
dijsktra();
for (int i=1;i<=n;++i)
line2[i].cost=dis[i];
zhengjie_wo_wu_di_la_hahaha_kruskal();
}
return 0;
}