P1186 玛丽卡

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
int d1[10001];
int d2[10001];
int v[10001];
int d[10001];
int pt[10001];
int to[1001][1001];
int  p[10001];
int cnt;
void add(int x,int y,int ww)
{
	to[x][y]=to[y][x]=ww;
}
void dijkstra(int st)
{
	for(int i=1; i<=n; i++)
	{
		d[i]=inf;
		v[i]=0;
	}
	d[st]=0;p[st]=0;
	for(int X=1; X<=n; X++)
	{
		int x=-inf;
		for(int i=1; i<=n; i++)
		{
			if(v[i]==1)continue;
			if(x==-inf||d[i]<d[x])x=i;
		}
		v[x]=1;
		//cout<<x<<endl;
		for(int i=1; i<=n; i++)
		{
			int y=i;
			if(v[y])continue;
			if(to[x][i]==inf)continue;
			if(d[y]>d[x]+to[x][i])
			{
				//cout<<to[x][i]<< " ";
				p[y]=x;
				d[y]=d[x]+to[x][i];
			}
		}
		//cout<<endl;
	}
	//for(int i=1; i<=n; i++)cout<<d[i]<<" ";
//	cout<<endl;
	if(st==1)for(int i=1; i<=n; i++)d1[i]=d[i];
	else     for(int j=1; j<=n; j++)d2[j]=d[j];
}
int tree[10001<<4];
void build(int k,int l,int r)
{
	tree[k]=inf;
	if(l==r)return;
	int mid=l+r>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
}
void update(int k,int l,int r,int x,int y,int z)
{
	if(l==x&&r==y)
	{
		tree[k]=min(tree[k],z);
		return;
	}
	int mid=l+r>>1;
	if(y<=mid)
	{
		update(k<<1,l,mid,x,y,z);
		return;
	}
	if(x>mid)
	{
		update(k<<1|1,mid+1,r,x,y,z);
		return;
	}
	update(k<<1,l,mid,x,mid,z);
	update(k<<1|1,mid+1,r,mid+1,y,z);
}
int query(int k,int l,int r,int x)
{
    if(l==r) return tree[k];
    int mid=(l+r)>>1;
    if(x<=mid)
		return min(query(k<<1,l,mid,x),tree[k]);
	else
        return min(query(k<<1|1,mid+1,r,x),tree[k]);
}
int fa[10001];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
} 
int main()
{
	//freopen("text.in","r",stdin);
	memset(to,0x3f3f3f3f,sizeof(to));
	cin>>n>>m;
	for(int i=1; i<=m; i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	/*for(int i=1; i<=n; i++)
	{
		for(int j=h[i]; j; j=nt[j])cout<<to[j]<<" ";
		cout<<endl;
	}*/
	dijkstra(n);
	dijkstra(1);
	for(int i=1; i<=n; i++)fa[i]=p[i];
	int NUM=0;
	for(int i=n; i>=1; i=p[i])
	{
		fa[i]=i;
		pt[i]=++NUM;
		if(p[i])
		{
			to[i][p[i]]=to[p[i]][i]=inf;
		}
	}
	//for(int i=1; i<=n; i++)cout<<fa[i]<<" ";
	build(1,1,n);
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			if(i==j)continue;
			if(to[i][j]==inf)continue;
			int len=min(d1[i]+d2[j]+to[i][j],to[i][j]+d1[j]+d2[i]);
			int x=pt[find(i)],y=pt[find(j)];
			if(x==y)continue;
			if(x>y)swap(x,y);
			update(1,1,NUM,x+1,y,len);
		}
	}
	int ans=d1[n];
	for(int i=2; i<=n; i++)
	ans=max(ans,query(1,1,NUM,i));//,printf("%d\n",query(1,1,NUM,i));
	cout<<ans<<endl;
}

原文地址：http://www.cnblogs.com/dadidididi/p/16794922.html