Safe Travel
64-bit integer IO format: %lld Java class name: Main
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
Input
* Lines 2..M+1: Three space-separated integers: a_i, b_i, and t_i
Output
Sample Input
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3
Sample Output
3
3
6
这道题是世界上第一道树链剖分的题目,我用左偏树AC了。
考虑先建一棵最短路树,一个点去掉树边后,它到根节点的距离就由它的子节点和它自己由非树边连到它这棵子树外的节点来更新,可以维护可并堆。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=;
const int maxm=;
int cnt,fir[maxn],to[maxm],nxt[maxm],val[maxm];
void addedge(int a,int b,int c){
nxt[++cnt]=fir[a];to[cnt]=b;fir[a]=cnt;val[cnt]=c;
} int tot,rt[maxm],key[maxm],lik[maxm],ch[maxm][],dep[maxm];
int ans[maxn],dis[maxn],add[maxm]; void Add(int x,int d){
if(!x)return;
key[x]+=d;
add[x]+=d;
} void Push_down(int x){
Add(ch[x][],add[x]);
Add(ch[x][],add[x]);
add[x]=;
} int Merge(int x,int y){
if(!x||!y)return x|y;
if(key[x]>key[y])swap(x,y);
Push_down(x);
ch[x][]=Merge(ch[x][],y);
if(dep[ch[x][]]<dep[ch[x][]])
swap(ch[x][],ch[x][]);
dep[x]=dep[ch[x][]]+;
return x;
} void Delete(int node){
Push_down(rt[node]);
rt[node]=Merge(ch[rt[node]][],ch[rt[node]][]);
} int ID[maxn],end[maxn],id; void DFS(int node){
ID[node]=++id;
for(int i=fir[node];i;i=nxt[i])
if(dis[to[i]]==dis[node]+val[i])
DFS(to[i]);
end[node]=id;
} void Solve(int node){
for(int i=fir[node];i;i=nxt[i]){
if(dis[to[i]]==dis[node]+val[i]){
Solve(to[i]);
Add(rt[to[i]],val[i]);
rt[node]=Merge(rt[node],rt[to[i]]);
}
else{
if(dis[to[i]]+val[i]==dis[node])continue;
if(ID[to[i]]<=end[node]&&ID[to[i]]>=ID[node])continue;
key[++tot]=dis[to[i]]+val[i];lik[tot]=to[i];
rt[node]=Merge(rt[node],tot);
}
}
while(rt[node]&&ID[lik[rt[node]]]<=end[node]&&ID[lik[rt[node]]]>=ID[node]){
Delete(node);
}
if(rt[node])
ans[node]=key[rt[node]];
}
struct Node{
int d,n;
Node(int d_=,int n_=){
d=d_;n=n_;
}
bool operator <(const Node &b)const{
return d>b.d;
}
}; priority_queue <Node,vector<Node> >q; int main(){
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
int n,m;
dep[]=-;
scanf("%d%d",&n,&m);
for(int i=,a,b,c;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
memset(dis,,sizeof(dis));
q.push(Node(,));dis[]=;
while(!q.empty()){
Node x=q.top();q.pop();
for(int i=fir[x.n];i;i=nxt[i]){
if(dis[x.n]+val[i]<dis[to[i]]){
dis[to[i]]=dis[x.n]+val[i];
q.push(Node(dis[to[i]],to[i]));
}
}
}
DFS();
Solve();
for(int i=;i<=n;i++)
printf("%d\n",ans[i]==?-:ans[i]);
return ;
}