BZOJ2069
描述
在Byte山的山脚下有一个洞穴入口. 这个洞穴由复杂的洞室经过隧道连接构成. 洞穴的入口是一条笔直通向“前面洞口”的道路. 隧道互相都不交叉(他们只在洞室相遇). 两个洞室要么就通过隧道连接起来,要么就经过若干隧道间接的相连. 现在决定组织办一个'King's of Byteotia Cup' 比赛. 参赛者的目标就是任意选择一条路径进入洞穴并尽快出来即可. 一条路径必须经过除了“前面洞口”之外还至少要经过其他一个洞室.一条路径中一个洞不能重复经过(除了“前面洞室”以外),类似的一条隧道也不能重复经过. 一个著名的洞穴探险家 Byteala 正准备参加这个比赛. Byteala 已经训练了数月而且他已获得了洞穴系统的一套详细资料. 对于每条隧道他都详细计算了从两个方向经过所需要的时间. 经过一个洞室的时间很短可以忽略不记. 现在Byteala 向计算一条符合条件的最优路径.
输入
第一行有两个数n 和 m (3 <= n <= 5000, 3 <= m <= 10000) 分别表示洞室的数目以及连接他们的隧道的数目. 洞室从1 到 n编号. “前面洞室”的编号为1. 接下来m 行描述了所有的隧道. 每行四个整数a,b,c,d 表示从洞室a到洞室b需要c分钟的时间,而从洞室b到洞室a需要d分钟的时间, 1 <= a,b <= n, a <> b, 1 <= c,d <= 10000. 你可以假设符合要求的路径肯定存在.
输出
输出一行,最少需要多少时间完成比赛.
输入样例 1
3 3 1 2 4 3 2 3 4 2 1 3 1 1
输出样例 1
6
来源
给大家提供一个测评地点吧：https://www.luogu.org/problemnew/show/T79047，大家也可以加入我的团队。数据均随机生成，生成数据的代码为：
#include <cstdio>
#include <ctime>
#include <algorithm>
using namespace std;
const int MAXN=10000;
int n,m,k;
int main()
{
srand((unsigned)time(NULL));
n=rand()%4997+13;m=rand()%9997+3;
printf("%d %d
",n,m);
k=rand()%(m/2)+2;
for (int i=1;i<=k;i++)
{
if (rand()%2==1) printf("1 %d %d %d
",rand()%n+1,rand()%MAXN+1,rand()%MAXN+1);
else printf("%d 1 %d %d
",rand()%n+1,rand()%MAXN+1,rand()%MAXN+1);
}
int u,v;
for (int i=k+1;i<=m;i++)
{
u=rand()%n+1;v=rand()%n+1;
while (v==n)v=rand()%n+1;
printf("%d %d %d %d
",u,v,rand()%MAXN+1,rand()%MAXN+1);
}
return 0;
}
这个题目的意思是，从洞口$1$进入，经过其他至少$1$个洞口后，再从洞口$1$出来，每个洞口只能经过一次（洞口$1$除外）。求最短路径。
这道题目由于起点和终点一样，我们一般的$SPFA$、$dijkstra$等等都不管用了，更可恶的是，由于每条边方向不同，权值也不同，这使得$Floyd$也不好用了。那么，我们该怎么办呢？
我们要把它转化为求普通的最短路！
我们把与顶点$1$相连的点记录下来，分别求最短路，然后再加上到点1的距离就行了。于是，你会惊奇的发现$Time~Limit~Exceeded$。那怎么办呢？？
我们可以把与$1$相连的点分为两组，一下求这么多的最短路。对与分组，二进制枚举就可以了。
AC代码：
#include <queue>
#include <cstdio>
#include <bitset>
#include <cstring>
using namespace std;
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return x*f;
}
const int MAXN=5005;
const int MAXM=20005;
int n,m,c,id,now,fir;
struct Qu
{
int dot,dis;
bool operator < (const Qu tmp) const
{
return dis>tmp.dis;
}
};
struct edge
{
int v,w,nx;
}set[MAXM],key[MAXN];
int head[MAXN],dis[MAXN];
bitset<MAXN> vis;
priority_queue<Qu> Q;
inline void Addedge(int u,int v,int w)
{
id++;set[id].v=v;set[id].w=w;set[id].nx=head[u];
head[u]=id;
}
inline void insert_edge(int v,int w)
{
now++;key[now].v=v;key[now].w=w;key[now].nx=fir;
fir=now;
}
inline void init()
{
int u,v,a,b;
n=read();m=read();
for (int i=1;i<=m;i++)
{
u=read();v=read();a=read();b=read();
Addedge(u,v,a);Addedge(v,u,b);
if (u==1)insert_edge(v,b);
if (v==1)insert_edge(u,a);
}
int x=n;
while (x>0) {c++;x/=2;}
}
inline void dijkstra()
{
vis.reset();vis.set(1);
for (int k=head[1];k>0;k=set[k].nx) Q.push((Qu){set[k].v,dis[set[k].v]});
int u,v;
while (!Q.empty())
{
u=Q.top().dot;Q.pop();
vis.set(u);
for (int k=head[u];k>0;k=set[k].nx)
{
v=set[k].v;
if (dis[u]+set[k].w<dis[v])
{
dis[v]=dis[u]+set[k].w;
if (!vis[v])Q.push((Qu){v,dis[v]});
}
}
}
}
int main()
{
init();
int ans=0x3f3f3f3f;
for (int i=(1<<c);i>0;i>>=1)
{
memset(dis,0x3f,sizeof(dis));
for (int k=head[1];k>0;k=set[k].nx)
if (set[k].v&i)dis[set[k].v]=set[k].w;
dijkstra();
for (int k=fir;k>0;k=key[k].nx)
if (~key[k].v&i)ans=min(ans,dis[key[k].v]+key[k].w);
memset(dis,0x3f,sizeof(dis));
for (int k=head[1];k>0;k=set[k].nx)
if (~set[k].v&i)dis[set[k].v]=set[k].w;
dijkstra();
for (int k=fir;k>0;k=key[k].nx)
if (key[k].v&i)ans=min(ans,dis[key[k].v]+key[k].w);
}
printf("%d
",ans);
return 0;
}
然后，我们需要证明这个方案的正确性。
首先，我们很容易想到第一版无脑枚举，就是枚举起点和终点，这样的话，枚举的复杂度是$(n*n)$，再加上$dijkstra$的时间复杂度$O(n*n)$，总的时间复杂度就是$O(n^4)$。但这种方法可以$TLE$飞。于是，便要进行一点优化：先枚举起点，求一遍最短路并通过$dis_i$数组记录从起点到点$i$的距离，时间复杂度便是$O(n^3)$，效率是有一点提高，但本题的数据实在是太坑了，这个算法也被卡掉了。
所以还要找更加优化的算法。我们可以把数字的二进制列出来：
| 十进制数 | 二进制数 |
| $1$ | $1$ |
| $2$ | $10$ |
| $3$ | $11$ |
| $4$ | $100$ |
| $5$ | $101$ |
| $6$ | $110$ |
| $7$ | $111$ |
| $8$ | $1000$ |
| $.~.~.$ | $.~.~.$ |