[USACO21DEC] Tickets P
首先我们思考暴力的 \(O(n^2)\) 怎么做。显然比起每次以 \(i\) 为起点跑 \(n\) 遍最短路,建反图后分别以 \(1\) 和 \(n\) 为起点跑两遍最短路是更加经济的方式。然后你可能会以为 \(\text{dis}(1,i)+\text{dis}(n,i)\) 就是答案了,之后你就会发现连样例都过不去。
为什么呢?假如说 \(n=4\),\(i=3\),此时 \(\text{path}(1,3)=1\to2\to3\),而 \(\text{path}(3,4)=3\to2\to4\),那么 \((2,3)\) 这条边就算重了。
如何解决?方法是将 \((\forall i)~\text{dis}(1,i)+\text{dis}(n,i)\) 作为每个点的初始 \(\text{dis}\),然后再跑一遍最短路,此时得到的 \(\text{dis}_i\) 就是每个点的答案了。然后你又会发现一个问题,就是某些点它转移不到。所以建边的时候一定是先把当前点和一个虚点连一条有花费的边,再把虚点和区间上的所有点连边权为 0 的边。这样跑出来的就是正确的。
37pts 就有了。
怎么优化到 100pts?线段树优化建图即可。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
#define INF 0x3f3f3f3f3f3f3f3fll
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
using ll=long long;
using pli=pair<ll,int>;
constexpr int MAXN=4e5+5;
int n,k,tn;
struct Tik{
int c,p,a,b;
}t[MAXN];
int head[MAXN],tot;
struct{
int v,to,w;
}e[5000005];
void addedge(int u,int v,int w){
e[++tot]={v,head[u],w};
head[u]=tot;
}
ll dis[MAXN],d[MAXN];
bool vis[MAXN];
priority_queue<pli>q;
void dijkstra(int s,bool sh=0){
memset(vis,0,sizeof(bool)*(tn+k+5));
if(!sh){
memset(dis,0x3f,sizeof(ll)*(tn+k+5));
dis[s]=0;
q.emplace(0,s);
}else{
memcpy(dis,d,sizeof(ll)*(tn+k+5));
for(int i=1;i<=tn+k;++i)
q.emplace(-dis[i],i);
}
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].to)
if(dis[e[i].v]>dis[u]+e[i].w){
dis[e[i].v]=dis[u]+e[i].w;
q.emplace(-dis[e[i].v],e[i].v);
}
}
}
#define lp p<<1
#define rp p<<1|1
struct{
struct SegTree{
int l,r,ls,rs;
}st[MAXN];
int build(int s,int t){
if(s==t) return st[s]={s,t,0,0},s;
int mid=(s+t)>>1,x=++tn;
st[x]={s,t,build(s,mid),build(mid+1,t)};
addedge(st[x].ls,x,0);
addedge(st[x].rs,x,0);
return x;
}
void update(int l,int r,int x,int p){
if(l<=st[p].l&&st[p].r<=r) return addedge(p,x,0);
int mid=(st[p].l+st[p].r)>>1;
if(l<=mid) update(l,r,x,st[p].ls);
if(mid<r) update(l,r,x,st[p].rs);
}
}T;
int main(){
n=tn=read(),k=read();
int rt=T.build(1,n);
for(int i=1;i<=k;++i){
t[i]={read(),read(),read(),read()};
addedge(tn+i,t[i].c,t[i].p);
T.update(t[i].a,t[i].b,tn+i,rt);
}
dijkstra(1);
memcpy(d,dis,sizeof(ll)*(tn+k+5));
dijkstra(n);
for(int i=1;i<=tn+k;++i) d[i]+=dis[i];
dijkstra(1,1);
for(int i=1;i<=n;++i) write(d[i]>=INF?-1:dis[i]);
return fw,0;
}
标签:Tickets,int,题解,void,tn,MAXN,text,USACO21DEC,dis
From: https://www.cnblogs.com/laoshan-plus/p/18530663