#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;
}
标签:10001,pt,int,玛丽,add,P1186,inf,d1
From: https://www.cnblogs.com/dadidididi/p/16794922.html