这题

我的思路是对于反图建一颗最短路树，然后对于每次删边都只会删除最短路树上的一条边，重新计算该子树所有节点的最短路。

但是这样做明显会有问题：

1. 可能删边后，这颗子树的一个子节点的最短路会到另一个子节点去。这种情况没有处理。

2. 虽然算完最短路后重新按照我的方法计算删边后的最短路复杂度是 $O(n+m)$ 的，但是有可能很多重边，会被卡掉。这个情况其实稍微改一改就好了，可能数据真的水吧。

但是问题1不知道怎么改，好像思路有亿些问题，不理解/kk

有做过这题的巨佬帮我看一看吗/kk

hack数据没构造出来，但是又感觉确实有hack数据，而且数据范围那么大也没出问题……

代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
#define int long long

typedef std::pair<int, int> PII;
std::priority_queue<PII, std::vector<PII>, std::greater<PII> > q;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, w, nxt;
} e[400005], e2[400005];
int head[200005], head2[200005], dis[200005], path[200005], tot, tot2, n, m;
bool done[200005];
std::vector<int> vec[200005];
inline void AddEdge(const int u, const int v, const int w) {
	e[++ tot].to = v, e[tot].w = w, e[tot].nxt = head[u], head[u] = tot;
}
inline void AddEdge2(const int u, const int v, const int w) {
	e2[++ tot2].to = v, e2[tot2].w = w, e2[tot2].nxt = head2[u], head2[u] = tot2;
}

void Dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	q.push(std::make_pair(dis[1] = 0, 1));
	while (q.size()) {
		int u(q.top().second);
		q.pop();
		if (done[u]) continue;
		done[u] = true;
		for (int i(head2[u]); i; i = e2[i].nxt) {
			int v(e2[i].to);
			if (dis[u] + e2[i].w < dis[v])
				q.push(std::make_pair(dis[v] = dis[u] + e2[i].w, v)), path[v] = u;
			else if (dis[u] + e2[i].w == dis[v] && u < path[v]) path[v] = u;
		}
	}
}
int dfs(const int u, const int fa) {
	int ans(1e18);
	for (int i(head[u]); i; i = e[i].nxt)
		if (e[i].to != fa && path[e[i].to] != u) ans = min(ans, dis[e[i].to] + e[i].w);
		else if (e[i].to != fa) ans = min(ans, dfs(e[i].to, u) + e[i].w);
	return ans;
}

signed main() {
	int ans(1e18);
	scanf("%lld%lld", &n, &m);
	for (int i(1); i <= m; ++ i) {
		int s, t, w, v;
		scanf("%lld%lld%lld%lld", &s, &t, &w, &v);
		AddEdge(s, t, w), AddEdge(t, s, v);
		AddEdge2(s, t, v), AddEdge2(t, s, w);
	}
	Dijkstra();
	for (int i(head[1]); i; i = e[i].nxt)
		ans = min(ans, e[i].w + dfs(e[i].to, 1)), vec[e[i].to].push_back(e[i].w);
	for (int i(1); i <= n; ++ i) if (vec[i].size() >= 2) {
		std::sort(vec[i].begin(), vec[i].end());
		ans = min(ans, vec[i][0] + vec[i][1]);
	}
	printf("%lld", ans);
	return 0;
}