洛谷—— P2934 [USACO09JAN]安全出行Safe Travel || COGS ——279|| BZOJ—

洛谷—— P2934 [USACO09JAN]安全出行Safe Travel || COGS ——279|| BZOJ——1576

https://www.luogu.org/problem/show?pid=2934

题目描述

Gremlins have infested the farm. These nasty, ugly fairy-like

creatures thwart the cows as each one walks from the barn (conveniently located at pasture_1) to the other fields, with cow_i traveling to from pasture_1 to pasture_i. Each gremlin is personalized and knows the quickest path that cow_i normally takes to pasture_i. Gremlin_i waits for cow_i in the middle of the final cowpath of the quickest route to pasture_i, hoping to harass cow_i.

Each of the cows, of course, wishes not to be harassed and thus chooses an at least slightly different route from pasture_1 (the barn) to pasture_i.

Compute the best time to traverse each of these new not-quite-quickest routes that enable each cow_i that avoid gremlin_i who is located on the final cowpath of the quickest route from pasture_1 to

pasture_i.

As usual, the M (2 <= M <= 200,000) cowpaths conveniently numbered 1..M are bidirectional and enable travel to all N (3 <= N <= 100,000) pastures conveniently numbered 1..N. Cowpath i connects pastures a_i (1 <= a_i <= N) and b_i (1 <= b_i <= N) and requires t_i (1 <= t_i <= 1,000) time to traverse. No two cowpaths connect the same two pastures, and no path connects a pasture to itself (a_i != b_i). Best of all, the shortest path regularly taken by cow_i from pasture_1 to pasture_i is unique in all the test data supplied to your program.

By way of example, consider these pastures, cowpaths, and [times]:

1--[2]--2-------+

| | | [2] [1] [3]

| | | +-------3--[4]--4

TRAVEL BEST ROUTE BEST TIME LAST PATH

p_1 to p_2 1->2 2 1->2

p_1 to p_3 1->3 2 1->3

p_1 to p_4 1->2->4 5 2->4

When gremlins are present:

TRAVEL BEST ROUTE BEST TIME AVOID

p_1 to p_2 1->3->2 3 1->2

p_1 to p_3 1->2->3 3 1->3

p_1 to p_4 1->3->4 6 2->4

For 20% of the test data, N <= 200.

For 50% of the test data, N <= 3000.

TIME LIMIT: 3 Seconds

MEMORY LIMIT: 64 MB

Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的地是牛棚_i).每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经.所以它们在牛_i到牛棚_i之前的最后一条牛路上等牛_i. 当然,牛不愿意遇到Gremlins,所以准备找一条稍微不同的路经从牛棚_1走到牛棚_i.所以,请你为每一头牛_i找出避免gremlin_i的最短路经的长度. 和以往一样, 农场上的M (2 <= M <= 200,000)条双向牛路编号为1..M并且能让所有牛到达它们的目的地, N(3 <= N <= 100,000)个编号为1..N的牛棚.牛路i连接牛棚a_i (1 <= a_i <= N)和b_i (1 <= b_i <= N)并且需要时间t_i (1 <=t_i <= 1,000)通过. 没有两条牛路连接同样的牛棚,所有牛路满足a_i!=b_i.在所有数据中,牛_i使用的牛棚_1到牛棚_i的最短路经是唯一的.

输入输出格式

输入格式：

Line 1: Two space-separated integers: N and M
Lines 2..M+1: Three space-separated integers: a_i, b_i, and t_i

输出格式：

Lines 1..N-1: Line i contains the smallest time required to travel from pasture_1 to pasture_i+1 while avoiding the final cowpath of the shortest path from pasture_1 to pasture_i+1. If no such path exists from pasture_1 to pasture_i+1, output -1 alone on the line.

输入输出样例

输入样例#1：

输出样例#1：

3 
3 
6

说明

感谢 karlven 提供翻译。

正解最短路径生成树+树剖（并查集可水过~、、、）

先用Dijkstra计算dis 以及最短路径的最后一条边，

对于这两点u,v,(无向边看做两条有向边)求出lca（u，v），，

则对于lca--v这条路径每个点,都可以由u到达，路径上的上的dis[x]'=dis[u]+dis[v]+edge[i].dis-dis[x](画图意会)

用树剖（并查集）维护最小值

  1 #include <algorithm>
  2 #include <cstdio>
  3 #include <queue>
  4 
  5 using namespace std;
  6 
  7 const int INF(0x3f3f3f3f);
  8 const int M(6e5+5);
  9 const int N(4e5+5);
 10 int n,m;
 11 
 12 int head[N],sumedge=1;
 13 struct Edge
 14 {
 15     int u,v,next,w;
 16     Edge(int u=0,int v=0,int next=0,int w=0):
 17         u(u),v(v),next(next),w(w){}
 18 }edge[M<<1];
 19 inline void ins(int u,int v,int w)
 20 {
 21     edge[++sumedge]=Edge(u,v,head[u],w);
 22     head[u]=sumedge;
 23 }
 24 
 25 struct Node
 26 {
 27     int id,dis;
 28     bool operator < (const Node &x) const
 29     {
 30         return dis>x.dis;
 31     }
 32     
 33 };
 34 priority_queue<Node>que;
 35 bool vis[N],mark[N];
 36 int dis[N],pre[N];
 37 inline void Dijkstra()
 38 {
 39     
 40     for(int i=0;i<=n;i++) dis[i]=INF;
 41     dis[1]=0;
 42     que.push((Node){1,0});
 43     for(;!que.empty();)
 44     {
 45         int u=que.top().id;
 46         que.pop();
 47         if(vis[u]) continue;
 48         vis[u]=1;
 49         for(int i=head[u];i;i=edge[i].next)
 50         {
 51             int v=edge[i].v;
 52             if(dis[v]>dis[u]+edge[i].w)
 53             {
 54                 dis[v]=dis[u]+edge[i].w;
 55                 mark[pre[v]]=0;
 56                 mark[i]=1;
 57                 pre[v]=i;
 58                 que.push((Node){v,dis[v]});
 59             }
 60         }
 61     }
 62 }
 63 
 64 int size[N],deep[N],dad[N],top[N],son[N],cnt,id[N],dfn[N];
 65 void DFS(int x,int fa,int deepth)
 66 {
 67     size[x]=1; deep[x]=deepth; dad[x]=fa;
 68     for(int i=head[x];i;i=edge[i].next)
 69         if(mark[i])
 70         {
 71             int v=edge[i].v;
 72             if(fa==v) continue;
 73             DFS(v,x,deepth+1);
 74             size[x]+=size[v];
 75             if(size[son[x]]<size[v]) son[x]=v;
 76         }
 77 }
 78 void DFS_(int x,int Top)
 79 {
 80     id[x]=++cnt; dfn[cnt]=x;
 81     top[x]=Top;
 82     if(son[x]) DFS_(son[x],Top);
 83     for(int i=head[x];i;i=edge[i].next)
 84         if(mark[i])
 85         {
 86             int v=edge[i].v;
 87             if(dad[x]!=v&&son[x]!=v) DFS_(v,v);
 88         }
 89 }
 90 int LCA(int x,int y)
 91 {
 92     for(;top[x]!=top[y];x=dad[top[x]])
 93         if(deep[top[x]]<deep[top[y]]) swap(x,y);
 94     return deep[x]<deep[y]?x:y;
 95 }
 96 
 97 struct Tree
 98 {
 99     int l,r,minn,flag;
100 }tr[N<<2];
101 #define lc (now<<1)
102 #define rc (now<<1|1)
103 #define mid (tr[now].l+tr[now].r>>1)
104 inline void Tree_up(int now)
105 {
106     tr[now].minn=min(tr[lc].minn,tr[rc].minn);
107 }
108 void Tree_build(int now,int l,int r)
109 {
110     tr[now].l=l; tr[now].r=r;
111     tr[now].minn=INF;
112     tr[now].flag=INF;
113     if(l==r) return ;
114     Tree_build(lc,l,mid);
115     Tree_build(rc,mid+1,r);
116 }
117 inline void Tree_down(int now)
118 {
119     if(tr[now].flag==INF) return ;
120     tr[lc].flag=min(tr[lc].flag,tr[now].flag);
121     tr[rc].flag=min(tr[rc].flag,tr[now].flag);
122     tr[lc].minn=min(tr[lc].minn,tr[lc].flag);
123     tr[rc].minn=min(tr[rc].minn,tr[rc].flag);
124 }
125 void Tree_change(int now,int l,int r,int x)
126 {
127     if(tr[now].l==l&&tr[now].r==r)
128     {
129         tr[now].minn=min(tr[now].minn,x);
130         tr[now].flag=min(tr[now].flag,x);
131         return ;
132     }
133     Tree_down(now);
134     if(r<=mid) Tree_change(lc,l,r,x);
135     else if(l>mid) Tree_change(rc,l,r,x);
136     else Tree_change(lc,l,mid,x),Tree_change(rc,mid+1,r,x);
137     Tree_up(now);
138 }
139 int Tree_query(int now,int to)
140 {
141     if(tr[now].l==tr[now].r) return tr[now].minn;
142     Tree_down(now);
143     if(to<=mid) return Tree_query(lc,to);
144     else return Tree_query(rc,to);
145 }
146 inline void List_change(int u,int v,int w)
147 {
148     int fx=top[u] ;
149     while(deep[fx]>deep[v])
150     {
151         Tree_change(1,id[top[u]],id[u],w);
152         u=dad[fx],fx=top[u];
153     }
154     if(u!=v) Tree_change(1,id[v]+1,id[u],w);
155 }
156 
157 int main()
158 {
159     freopen("travel.in","r",stdin);
160     freopen("travel.out","w",stdout);
161     
162     scanf("%d%d",&n,&m);
163     for(int a,b,t,i=1;i<=m;i++)
164     {
165         scanf("%d%d%d",&a,&b,&t);
166         ins(a,b,t); ins(b,a,t);
167     }
168     Dijkstra();
169     DFS(1,0,1);
170     DFS_(1,1);
171     Tree_build(1,1,cnt);
172     for(int lca,u,v,i=2;i<=sumedge;i+=2)
173     {
174         u=edge[i].u,v=edge[i].v,lca=LCA(u,v);
175         if(!mark[i]) List_change(v,lca,dis[u]+dis[v]+edge[i].w);
176         if(!mark[i^1]) List_change(u,lca,dis[u]+dis[v]+edge[i].w);
177     }
178     for(int i=2;i<=n;i++)
179     {
180         int tmp=Tree_query(1,id[i]);
181         if(tmp==INF) puts("-1");
182         else printf("%d
",tmp-dis[i]);
183     }
184     return 0;
185 }

唉、

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。