注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 3047 & bzoj 2125 & 清澄 1268 最短路(杨天)  

2013-11-02 15:24:13|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://pan.baidu.com/s/1wzCpC

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define maxn 10010
#define maxm 50010
using namespace std;
int F[maxn][20],pos[maxn],dist[maxn],dep[maxn];
int n,m,q,dis[maxn],father[maxn],nCircle,Sum[maxn];
int nEdge=1,to[maxm],next[maxm],start[maxn],len[maxm];
int dfn[maxn],low[maxn],dfs_clock;
bool isDelete[maxm];
void make(int a,int b,int c)
{
nEdge++,to[nEdge]=b,next[nEdge]=start[a],start[a]=nEdge,len[nEdge]=c;
}
void read()
{
scanf("%d %d %d",&n,&m,&q);
for(int i=1,a,b,c;i<=m;++i)
{
scanf("%d %d %d",&a,&b,&c);
make(a,b,c),make(b,a,c);
}
}
void SPFA(int p)
{
static bool use[maxn];
static int queue[maxn];
int front=0,rear=1;
for(int i=1;i<=n;++i)
dist[i]=1<<30;
queue[rear]=p,dist[p]=0;
while(front!=rear)
{
use[p=queue[front=front%n+1]]=false;
for(int i=start[p];i;i=next[i])
if(dist[to[i]]>dist[p]+len[i])
{
dist[to[i]]=dist[p]+len[i];
if(use[to[i]]==false)
use[queue[rear=rear%n+1]=to[i]]=true;
}
}
}
void Change(int p,int q,int x)
{
++nCircle;
isDelete[x]=isDelete[x^1]=true,make(q,p,0),make(p,q,0);
Sum[nCircle]+=len[x];
for(int i=p;i!=q;i=to[father[i]^1])
{
pos[i]=nCircle;
isDelete[father[i]]=isDelete[father[i]^1]=true;
make(q,i,0),make(i,q,0);
Sum[nCircle]+=len[father[i]];
}
}
void Tarjan(int p,int fa)
{
dfn[p]=low[p]=++dfs_clock;
for(int i=start[p];i;i=next[i])
if((i^1)!=fa&&i<=m*2+1)
{
int q=to[i];
if(dfn[q]==0)
father[q]=i,dis[q]=dis[p]+len[i],Tarjan(q,i);
if(dfn[q]<dfn[p])
Change(p,q,i);
}
}
void BFS(int p)
{
static int queue[maxn];
static bool use[maxn];
int front=0,rear=1;
queue[rear]=p,dep[p]=1,use[p]=true;
while(front<rear)
{
int p=queue[++front];
for(int i=start[p];i;i=next[i])
if(use[to[i]]==false&&isDelete[i]==false)
{
int q=to[i];
use[q]=true;
dep[q]=dep[p]+1;
queue[++rear]=q;
F[q][0]=p;
for(int j=1;j<=18;++j)
F[q][j]=F[F[q][j-1]][j-1];
}
}
}
int solve(int a,int b)
{
if(dep[a]<dep[b])
swap(a,b);
int x=a,y=b;
for(int i=18;i>=0;--i)
if(dep[F[a][i]]>=dep[b])
a=F[a][i];
if(a==b)
return dist[x]-dist[b];
for(int i=18;i>=0;--i)
if(F[a][i]!=F[b][i])
a=F[a][i],b=F[b][i];
if(pos[a]&&pos[a]==pos[b])
{
int len=abs(dis[a]-dis[b]);
return dist[a]-dist[x]+dist[b]-dist[y]+min(len,Sum[pos[a]]-len);
}
return dist[x]+dist[y]-2*dist[F[a][0]];
}
void Query()
{
for(int i=1,a,b;i<=q;++i)
{
scanf("%d %d",&a,&b);
printf("%d\n",solve(a,b));
}
}
int main()
{
freopen("communicate.in","r",stdin);
freopen("communicate.out","w",stdout);
read();
SPFA(1);
Tarjan(1,-1);
BFS(1);
Query();
fclose(stdin);
fclose(stdout);
return 0;
}

  评论这张
 
阅读(926)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017