蒟蒻我原本还想着跑两边spfa，发现不行，就gg了。
首先这道题卡spfa，所以需要用堆优化的dijkstra求出最短路径
因为题目中说了，保证最短路径有且只有一条，所以可以通过dfs求出最短路径树
发现，需要给这课树加边，才能有别的路径到达一个点x
那么我们连接树上两个节点u，v，边权为w
发现，u，v到两点公共祖先的路径上的所有点（除去lca）的答案都会受到影响
且ans[i] = dis[u] + dis[v] + w - dis[i]
要使得ans最小，需要dis[u] + dis[v] + w最小，
那么直接树剖暴力修改不就好了？
另一种思路
我们可以把所有非树边取出，以dis[u] + dis[v] + w为关键字排一下，
显然，每一个点都只会求解一次，往后都不会更新答案
可以用并查集，已经更新答案的点就用并查集连接到lca，下次遇到已经更新过的点直接往上跳即可
找lca的过程和树剖类似
时间复杂度比树剖不知道高到哪里去了！
网上还有一些用左偏树或是单调队列做的，看样子好高深，蒟蒻没搞懂。。
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 200001
#define heap pair<int, int>
using namespace std;
int n, m, cnt, tot;
int head[N], to[N << 1], val[N << 1], next[N << 1], dis[N], deep[N], ans[N], pre[N], f[N];
bool vis[N << 1];
priority_queue <heap, vector <heap>, greater <heap> > q;
vector <int> g;
struct node
{
int x, y, z;
node(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) {}
}p[N << 1];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
}
inline void add(int x, int y, int z)
{
to[cnt] = y;
val[cnt] = z;
next[cnt] = head[x];
head[x] = cnt++;
}
inline void dijkstra()
{
int i, u, v;
memset(dis, 127, sizeof(dis));
dis[1] = 0;
q.push(make_pair(0, 1));
while(!q.empty())
{
u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(i = head[u]; i ^ -1; i = next[i])
{
v = to[i];
if(dis[v] > dis[u] + val[i])
{
dis[v] = dis[u] + val[i];
q.push(make_pair(dis[v], v));
}
}
}
}
inline void dfs(int u, int d)
{
int i, v;
deep[u] = d;
for(i = head[u]; i ^ -1; i = next[i])
{
v = to[i];
if(dis[v] == dis[u] + val[i])
{
vis[i] = vis[i ^ 1] = 1;
pre[v] = u;
dfs(v, d + 1);
}
}
}
inline bool cmp(node x, node y)
{
return dis[x.x] + dis[x.y] + x.z < dis[y.x] + dis[y.y] + y.z;
}
inline int find(int x)
{
return x == f[x] ? x : f[x] = find(f[x]);
}
int main()
{
int i, j, x, y, z, u, v;
n = read();
m = read();
memset(head, -1, sizeof(head));
for(i = 1; i <= m; i++)
{
x = read();
y = read();
z = read();
add(x, y, z);
add(y, x, z);
}
dijkstra();
memset(vis, 0, sizeof(vis));
dfs(1, 1);
for(u = 1; u <= n; u++)
for(i = head[u]; i ^ -1; i = next[i])
{
if(vis[i]) continue;
v = to[i];
vis[i] = vis[i ^ 1] = 1;
p[++tot] = node(u, v, val[i]);
}
sort(p + 1, p + tot + 1, cmp);
memset(ans, 127, sizeof(ans));
for(i = 1; i <= n; i++) f[i] = i;
for(i = 1; i <= tot; i++)
{
x = p[i].x;
y = p[i].y;
g.clear();
while(x ^ y)
{
if(deep[x] < deep[y]) x ^= y ^= x ^= y;
if(ans[x] <= 1e9) x = find(x);
else
{
ans[x] = dis[p[i].x] + dis[p[i].y] + p[i].z - dis[x];
g.push_back(x);
x = pre[x];
}
}
for(j = 0; j < g.size(); j++) f[g[j]] = find(x);
}
for(i = 2; i <= n; i++)
printf("%d
", ans[i] <= 1e9 ? ans[i] : -1);
return 0;
}