【题意】
给定一个无向图，找到1-i所有的次短路经，要求与最短路径的最后一条边不重叠。
【思路】
首先用dijkstra算法构造以1为根的最短路树。
将一条无向边看作两条有向边，考察一条不在最短路树上的边(u,v)，如果我们连接(u,v) ，设t=lct(u,v)，则为v->t（不含t）路径上的点提供了另外一条1-x的路径且最后一条边不与最短路重合，这条路径长度为dis[u]+dis[v]+e.w-dis[x]，对于每个点维护最小的mn=dis[u]+dis[v]+e.w，因为每次需要对一条路径进行修改，所以可以用树链剖分+线段树维护最小值和一个懒标记完成。
好题。。。
【代码】
#include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; typedef long long ll;
const int N = 2e5+;
const int M = 4e5+;
const int inf = 1e9; ll read() {
char c=getchar();
ll f=,x=;
while(!isdigit(c)) {
if(c=='-') f=-; c=getchar();
}
while(isdigit(c))
x=x*+c-'',c=getchar();
return x*f;
} struct Edge {
int u,v,w,nxt;
}e[M];
int en=,front[N];
void adde(int u,int v,int w) {
e[++en]=(Edge){u,v,w,front[u]}; front[u]=en;
} struct Node {
int id,dis;
bool operator < (const Node& rhs) const {
return dis>rhs.dis;
}
}; struct Tnode {
int u,l,r,mn,tag;
void minv(int x);
void pushdown();
void maintain();
}T[N<<];
void Tnode::minv(int x) {
tag=x;
mn=min(mn,x);
}
void Tnode:: pushdown() {
if(tag!=- && l!=r) {
T[u<<].minv(tag);
T[u<<|].minv(tag);
tag=-;
}
}
void Tnode:: maintain() {
if(l==r) return ;
mn=min(T[u<<].mn,T[u<<|].mn);
} priority_queue<Node> q;
int n,m;
int SZ,vis[N],dis[N],dep[N],siz[N],son[N],fa[N],top[N],mark[N],p[N],pl[N]; void dijkstra()
{
FOR(i,,n) dis[i]=inf;
dis[]=;
q.push((Node){,});
while(!q.empty()) {
int u=q.top().id; q.pop();
if(vis[u]) continue;
vis[u]=;
trav(u,i) {
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w) {
dis[v]=dis[u]+e[i].w;
mark[p[v]]=; mark[i]=;
p[v]=i;
q.push((Node){v,dis[v]});
}
}
}
}
void dfs1(int u)
{
siz[u]=; son[u]=;
trav(u,i) if(mark[i]) {
int v=e[i].v;
if(v!=fa[u]) {
fa[v]=u;
dep[v]=dep[u]+;
dfs1(v);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
}
void dfs2(int u,int tp)
{
top[u]=tp; pl[u]=++SZ;
if(son[u]) dfs2(son[u],tp);
trav(u,i) if(mark[i]&&e[i].v!=fa[u])
dfs2(e[i].v,e[i].v);
}
int lca(int u,int v) {
while(top[u]!=top[v]) {
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]? u:v;
}
void build(int u,int l,int r)
{
T[u]=(Tnode) {u,l,r,inf,-};
if(l==r) return ;
int mid=l+r>>;
build(u<<,l,mid),
build(u<<|,mid+,r);
}
void update(int u,int L,int R,int x)
{
T[u].pushdown();
if(L<=T[u].l&&T[u].r<=R) T[u].minv(x);
else {
int mid=T[u].l+T[u].r>>;
if(L<=mid) update(u<<,L,R,x);
if(mid<R) update(u<<|,L,R,x);
T[u].maintain();
}
}
int query(int u,int x)
{
T[u].pushdown();
if(T[u].l==T[u].r) return T[u].mn;
else {
int mid=T[u].l+T[u].r>>;
if(x<=mid) return query(u<<,x);
else return query(u<<|,x);
}
} void modify(int u,int v,int x)
{
while(top[u]!=top[v]) {
if(dep[top[u]]<dep[top[v]]) swap(u,v);
update(,pl[top[u]],pl[u],x);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
update(,pl[u],pl[v],x);
} int main()
{
n=read(),m=read();
int u,v,w;
FOR(i,,m) {
u=read(),v=read(),w=read();
adde(u,v,w),adde(v,u,w);
}
dijkstra();
dfs1(),dfs2(,);
build(,,SZ);
for(int i=;i<=en;i+=) {
u=e[i].u,v=e[i].v,w=e[i].w;
int LCA=lca(u,v);
if(!mark[i]) modify(v,LCA,dis[u]+dis[v]+e[i].w);
if(!mark[i^]) modify(u,LCA,dis[u]+dis[v]+e[i].w);
}
FOR(i,,n) {
w=query(,pl[i]);
if(w==inf) puts("-1");
else printf("%d\n",w-dis[i]);
}
return ;
}