题意也太不清楚了喂(#`O′),大溶洞指的是 \(1\) 号点这个关键信息都没翻译出来!而且也没说保证有解!
DarkBZOJ
嘛,首先我们正反图各跑一遍最短路肯定没问题,思考怎么算答案。
我们枚举边,然后通过两个方向的最短路来更新答案。牛逼性质是如果第一步走的不一样,那么就可以去更新答案,因为尽管它有可能重复经过一条边,但一定存在一个更优的走法不经过重复经过一条边。
这个牛逼性质画画图就可以证出来,或者你感性理解一下。
所以我们跑最短路的时候顺便记录一下第一步走的是哪条边(注意不能记录是哪个点,因为有重边),然后更新答案即可。
时间复杂度 \(O(n\log_2m)\)。
//12252024832524 #include <bits/stdc++.h> #define TT template<typename T> using namespace std; typedef long long LL; const int MAXN = 10005; const int MAXM = 200005; const int INF = 0x3f3f3f3f; int n,m,ans = INF; LL Read() { LL x = 0,f = 1;char c = getchar(); while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();} return x * f; } TT void Put1(T x) { if(x > 9) Put1(x/10); putchar(x%10^48); } TT void Put(T x,char c = -1) { if(x < 0) putchar('-'),x = -x; Put1(x); if(c >= 0) putchar(c); } TT T Max(T x,T y){return x > y ? x : y;} TT T Min(T x,T y){return x < y ? x : y;} TT T Abs(T x){return x < 0 ? -x : x;} int head[MAXN],tot = 1; struct edge{ int v,w,nxt; }e[MAXM<<1]; void Add_Edge(int u,int v,int w){ e[++tot] = edge{v,w,head[u]}; head[u] = tot; } int dis[2][MAXN]; struct node{ int x,d; bool operator < (const node &px)const{ return d > px.d; } }; int f[MAXN],g[MAXN]; int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); n = Read(); m = Read(); for(int i = 1,u,v;i <= m;++ i){ u = Read(); v = Read(); Add_Edge(u,v,Read()); Add_Edge(v,u,Read()); } for(int i = 1;i <= n;++ i) dis[0][i] = INF; priority_queue<node> q; q.push(node{1,dis[0][1] = 0}); while(!q.empty()){ node t = q.top(); q.pop(); if(t.d > dis[0][t.x]) continue; for(int i = head[t.x],v; i ;i = e[i].nxt) if(t.d+e[i].w < dis[0][v = e[i].v]){ if(t.x == 1) f[v] = i>>1; else f[v] = f[t.x]; q.push(node{v,dis[0][v] = t.d+e[i].w}); } } for(int i = 1;i <= n;++ i) dis[1][i] = INF; q.push(node{1,dis[1][1] = 0}); while(!q.empty()){ node t = q.top(); q.pop(); if(t.d > dis[1][t.x]) continue; for(int i = head[t.x],v; i ;i = e[i].nxt) if(t.d+e[i^1].w < dis[1][v = e[i].v]){ if(t.x == 1) g[v] = i>>1; else g[v] = g[t.x]; q.push(node{v,dis[1][v] = t.d+e[i^1].w}); } } for(int x = 1;x <= n;++ x) for(int i = head[x],v; i ;i = e[i].nxt) if(f[x] != g[v = e[i].v] && f[x] != (i >> 1) && g[v] != (i>>1)) ans = Min(ans,dis[0][x]+e[i].w+dis[1][v]); Put(ans,'\n'); return 0; }