题目
题目链接：https://darkbzoj.tk/problem/2407
探险家小T好高兴！X国要举办一次溶洞探险比赛，获奖者将得到丰厚奖品哦！小T虽然对奖品不感兴趣，但是这个大振名声的机会当然不能错过！
比赛即将开始，工作人员说明了这次比赛的规则：每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路，也有可能没有，但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发，并再次回到这个大溶洞。
如果就这么点限制，那么问题就太简单了，可是举办方又提出了一个条件：不能经过同一条暗道两次。这个条件让大家犯难了。这该怎么办呢？
到了大溶洞口后，小T愉悦地发现这个地方他曾经来过，他还记得有哪些暗道，以及通过每条暗道的时间。小T现在向你求助，你能帮他算出至少要多少时间才能回到大溶洞吗？
(nleq 10^4,mleq 2 imes 10^5)。
思路
两个做法。其中第一个做法并没有办法解决有重边且边权相同的情况。第二种做法可以解决。
先把从 (1) 开始的单元最短路径求出来，记录每一个点的最短路 (dis) 以及最短路中第一个点（不算 (1)）是哪一个点 (pre)。
然后考虑构造一张新图。对于原图中一条边 ((u,v,d))：
- 如果 (u=1,pre[v]=v)，说明到 (v) 的最短路就是 ((1,v,d)) 这一条边。那么忽略这一条边。
- 如果 (u=1,pre[v] eq v)，说明我们可以从 (1) 到 (v) 走这一条边并且不经过最短路上的边。连边 ((1,v,d))。
- 如果 (v=1,pre[u]=u)，这条边就是最短路，连边 ((u,n+1,d))。
- 如果 (v=1,pre[u] eq u)，那么可以走 (1,pre[u],u,n) 这一条路径，连边 ((1,n+1,dis[u]+d))。
- 如果 (u eq 1,v eq 1,pre[u]=pre[v])，那么就可以通过 (1) 到 (pre[u]) 的最短路，再加上 (pre[u]) 到 (1) 的另一条路。连边 ((u,v,d))。
- 如果 (u eq 1,v eq 1,pre[u] eq pre[v])，连边 ((1,v,dis[u]+d))。
然后跑新图的最短路，答案就是 (dis[n+1])。
这个构造方法很巧妙的把 (1) 到任意一个点的最短路和非最短路扔到了图的两边，保证不会重复经过。但是如果遇到这种数据：
2
1 2 1 1
1 2 1 1
就会因为最短路有两条而错误。但是 bzoj 的数据并没有这样的，可以通过。
时间复杂度 (O((n+m)log n))。
第二种算法则考虑到如果会走重复的路径，那么一定是 (1) 到某一个点的路走两次。
所以直接把一端是点 (1) 的路二进制分组一下，每次从一组开始往另一组跑最短路就行了。
时间复杂度 (O((n+m)log nlog m))。吸氧能过。
代码
算法一。算法二心情好就会补的。
#include <bits/stdc++.h>
#define mp make_pair
#define se second
using namespace std;
typedef long long ll;
const int N=10010,M=400010;
int n,m,tot,head[N],pre[N],U[M],V[M],D1[M],D2[M];
ll dis[N];
bool vis[N];
struct edge
{
int next,to;
ll dis;
}e[M];
void add(int from,int to,ll dis)
{
e[++tot]=(edge){head[from],to,dis};
head[from]=tot;
}
void addedge(int x,int y,int d)
{
if (x==1 && pre[y]!=y) add(1,y,d);
if (y==1 && pre[x]!=x) add(1,n+1,dis[x]+d);
if (y==1 && pre[x]==x) add(x,n+1,d);
if (x!=1 && y!=1 && pre[x]==pre[y]) add(x,y,d);
if (x!=1 && y!=1 && pre[x]!=pre[y]) add(1,y,dis[x]+d);
}
void dij()
{
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(vis,0,sizeof(vis));
priority_queue<pair<ll,int> > q;
q.push(mp(0,1)); dis[1]=0;
while (q.size())
{
int u=q.top().se; q.pop();
if (vis[u]) continue;
vis[u]=1;
for (int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if (dis[v]>dis[u]+e[i].dis)
{
dis[v]=dis[u]+e[i].dis; pre[v]=pre[u];
if (u==1) pre[v]=v;
q.push(mp(-dis[v],v));
}
}
}
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&U[i],&V[i],&D1[i],&D2[i]);
add(U[i],V[i],D1[i]); add(V[i],U[i],D2[i]);
}
dij();
memset(head,-1,sizeof(head));
tot=0;
for (int i=1;i<=m;i++)
{
addedge(U[i],V[i],D1[i]);
addedge(V[i],U[i],D2[i]);
}
dij();
cout<<dis[n+1];
return 0;
}