传送门
蒟蒻我原本还想着跑两边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 }p[N << 1]; inline int read() inline void add(int x, int y, int z) inline void dijkstra() } } } inline void dfs(int u, int d) } } inline bool cmp(node x, node y) inline int find(int x) int main() dijkstra(); memset(vis, 0, sizeof(vis)); dfs(1, 1); for(u = 1; u <= n; u++) for(i = head[u]; i ^ 1; i = next[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++) } for(j = 0; j < g.size(); j++) f[g[j]] = find(x); } for(i = 2; i <= n; i++) printf("%d\n", ans[i] <= 1e9 ? ans[i] : 1); return 0; }
上一篇：[BZOJ4756] [Usaco2017 Jan]Promotion Counting（线段树合并）
下一篇：[BZOJ1596] [Usaco2008 Jan]电话网络（树形DP || 贪心）
dfs stl 最短路 dijkstra 并查集 堆 线段树 树链剖分
