题目传送门(BZOJ)
>原文链接<

题解 :

Suika的二进制分组做法

考虑这样的一个暴力 : 对于原点走一次能到达的所有点, 切断这条边, 并从那个点到原点跑一次最短路, 然后留一个最小值.

我们发现这样在回到原点的最短路上做了很多的重复计算, 导致该算法的复杂度是不对的, 考虑重新建图来避免重复计算

我们先从1对图做一次最短路(SPFA或者Dijkstra均可), 预处理出每个到每个点的最短路Dis[i]和这条路上除了点1之外的第一个点pre[i]

建立虚拟汇点T, 对边进行分类讨论 :

  1. 对于一条边i:(u, 1, w):
    • pre[u] \ne u, 则代表着有一条路径1\to pre[u]\to u\to 1, 我们直接用dis[u]+val[i]更新答案(相当于加一条边(S, T, dis[u]+val[i]))
    • 否则, 我们可以从1\to p\to u\to 1. 其中p \ne u, 在图的意义上相当于连一条边(u, T, w), 并且不能再连(1, u)这条边了
  2. 对于一条边i:(1, v, w) :
    • pre[v] = v, 我们不用再连这条边了,因为到v的最短路径就是w, 同时也符合了上面的条件
    • 否则, 我们连一条边(1, v, w) , 因为第一次最短路并没有用到这条边
  3. 对于一条边i:(u, v, w):
    • pre[u]\ne pre[v]: 原点到u和到v所经过的第一条边不同, 存在1\to pre[u]\to u\to v\to 1的路径, 连边(1, v, dis[u]+w)
    • 否则保留边(u, v, w)

1\to T最短路即可

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define mp make_pair#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)using namespace std;char buf[100000], *p1, *p2; const int N = 41000, M = 410000;;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}struct Edge { int to, val; Edge *next;}*h[N], e[M];int f[N], vis[N], _, n, m;int pre[N], ra[N], rb[N], rc[N];inline void addEdge(int u, int v, int w) { Edge *tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; h[u] = tmp;}priority_queue<pair<int, int> > q;void Dijkstra() { while(!q.empty()) { int u = q.top().second; q.pop(); if(vis[u]) continue; vis[u] = 1; rev(i, u) if(f[i->to] > f[u]+i->val) { pre[i->to] = pre[u]; f[i->to] = f[u]+i->val; q.push(mp(-f[i->to], i->to)); } }}int main() { freopen("B.in", "r", stdin); freopen("B.out", "w", stdout); n = rd(), m = rd(); for(int i = 1; i <= m; i ++ ) { int u = rd(), v = rd(), w1 = rd(), w2 = rd(); addEdge(u, v, w1); ra[_] = u, rb[_] = v, rc[_] = w1; addEdge(v, u, w2); ra[_] = v, rb[_] = u, rc[_] = w2; } memset(f, 0x3f, sizeof f); f[1] = 0; rev(i, 1) { pre[i->to] = i->to; f[i->to] = i->val; q.push(mp(-i->val, i->to)); } Dijkstra(); memset(h, 0, sizeof h); _ = 0; int ans = 1<<30; for(int i = 1; i <= m << 1; i ++ ) { if(ra[i] == 1) { if(pre[rb[i]]!=rb[i]) addEdge(1, rb[i], rc[i]); } else if(rb[i]==1) { if(ra[i]!=pre[ra[i]]) ans=min(ans, f[ra[i]]+rc[i]); else addEdge(ra[i], n+1, rc[i]); } else { if(pre[ra[i]]==pre[rb[i]]) addEdge(ra[i], rb[i], rc[i]); else addEdge(1, rb[i], f[ra[i]]+rc[i]); } } memset(vis, 0, sizeof vis); memset(f, 0x3f, sizeof f); f[1] = 0; q.push(mp(0, 1)); Dijkstra(); ans = min(ans, f[n+1]); printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);}