记录编号	144259	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]最短路(杨天)	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.429 s
提交时间	2014-12-21 20:07:29	内存使用	5.90 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int SIZEN=10010,SIZEM=20010,SIZELOG=20;
int log_2(int x){
	int ans=-1;
	while(x) ans++,x>>=1;
	return ans;
}
class Edge{
public:
	int to,w,id;
	Edge(int to_=0,int w_=0,int id_=0){to=to_,w=w_,id=id_;}
};
int N,M,Q;
vector<Edge> G[SIZEN];
int father[SIZEN];
int grand_dis[SIZEN]={0};
int ring_len[SIZEM];//环的数量,每个环的长度
int dfn[SIZEN]={0},timer=0;
Edge step_up[SIZEN][SIZELOG];
vector<int> GT[SIZEN];
int depth[SIZEN];
int Dist(int a,int b){
	if(a==b) return 0;
	int m=log_2(N),ans=0,j;
	if(depth[a]>depth[b]) swap(a,b);//b较深
	j=m;
	while(depth[b]>depth[a]){
		while(j>=0&&depth[step_up[b][j].to]<=depth[a]) j--;
		if(j<0) j=0;
		ans+=step_up[b][j].w;
		b=step_up[b][j].to;
	}
	j=m;
	while(true){
		while(j>=0&&step_up[b][j].to==step_up[a][j].to) j--;
		if(j<0) break;
		ans+=step_up[a][j].w+step_up[b][j].w;
		a=step_up[a][j].to,b=step_up[b][j].to;
	}
	int len;
	if(step_up[a][0].id==step_up[b][0].id){//这时是最终走到一个环上,我们需要考虑环上距离
		len=abs(grand_dis[a]-grand_dis[b]);
		len=min(len,ring_len[step_up[a][0].id]-len);
	}
	else len=step_up[a][0].w+step_up[b][0].w;
	return ans+len;
}
void Process(void){
	int a,b;
	for(int i=1;i<=Q;i++){
		scanf("%d%d",&a,&b);
		printf("%d\n",Dist(a,b));
	}
}
void DFS_Tree(int x){
	for(int i=0;i<GT[x].size();i++){
		int u=GT[x][i];
		depth[u]=depth[x]+1;
		DFS_Tree(u);
	}
}
void Prepare(void){
	for(int i=1;i<=N;i++){
		int u=step_up[i][0].to;
		if(u) GT[u].push_back(i);
	}
	depth[1]=1;
	DFS_Tree(1);
	int m=log_2(N);
	for(int j=1;j<=m;j++){
		for(int i=1;i<=N;i++){
			int mid=step_up[i][j-1].to;
			step_up[i][j].to=step_up[mid][j-1].to;
			step_up[i][j].w=step_up[i][j-1].w+step_up[mid][j-1].w;
		}
	}
}
void Find_Ring(int x){
	dfn[x]=++timer;
	for(int i=0;i<G[x].size();i++){
		Edge &e=G[x][i];
		if(e.to==father[x]) continue;
		if(!dfn[e.to]){
			step_up[e.to][0]=Edge(x,e.w,e.id);
			grand_dis[e.to]=grand_dis[x]+e.w;
			father[e.to]=x;
			Find_Ring(e.to);
		}
		else if(dfn[e.to]<dfn[x]){//找到了一个环
			ring_len[e.id]=e.w+grand_dis[x]-grand_dis[e.to];
			for(int v=x;v!=e.to;v=father[v]){
				step_up[v][0].to=e.to;
				step_up[v][0].id=e.id;
				step_up[v][0].w=min(grand_dis[v]-grand_dis[e.to],ring_len[e.id]-(grand_dis[v]-grand_dis[e.to]));
			}
		}
	}
}
void Read(void){
	scanf("%d%d%d",&N,&M,&Q);
	int a,b,w;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&a,&b,&w);
		G[a].push_back(Edge(b,w,i));
		G[b].push_back(Edge(a,w,i));
	}
}
int main(){
	freopen("nt2011_path.in","r",stdin);
	freopen("nt2011_path.out","w",stdout);
	Read();
	Find_Ring(1);
	Prepare();
	Process();
	return 0;
}