Description：

无向图有一条边不能走，只有走到相邻节点时才能知道能不能走，问最坏情况下 $S$ 到 $T$ 的最短路。

$1\leqslant n\leqslant 10^5$

Solution：

首先建出反图的最短路树，那么如果删去的边不是最短路树上到父亲的边那么最短路不受影响，否则的话唯一的可能就是走到子树中的一个点然后跳到子树外面，因此对于每个点记一下走到子树外再走到根的最短距离，然后从下往上用可并堆打标记合并，这样我们就得到了从某个点如果父亲被封了再到根的最短路 $d'[i]$ 。

然后考虑怎么求解答案，设 $f[i]$ 表示从 $i$ 开始一定能到达 $T$ 的最短路，先枚举下一步走到的点 $v$ ，如果这条边没有被封，那么 $f[i]=f[v]+e(i,v)$ ，如果封了，那么如果 $v$ 在最短路树上是 $i$ 的父亲，那么 $f[i]=d'[i]$ ，否则 $f[i]=d[i]$ ，即： $$ f[i]=\min_{i\to v}\Big(\max(f[v]+e(i,v),v=par[i]?d[i]',d[i])\Big) $$ 然后就像 $dijkstra$ 那样每次去一个最小的更新就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m,st,ed;

#define MAXN 100010

#define MAXM 200010

typedef long long ll;

struct edge

{

	int to,nxt;

	ll v;

}ve[MAXM << 1];

int vedgenum = 0;

int vlin[MAXN] = {0};

void vadd(int a,int b,ll v)

{

	ve[++vedgenum] = (edge){b,vlin[a],v};vlin[a] = vedgenum;

	ve[++vedgenum] = (edge){a,vlin[b],v};vlin[b] = vedgenum;

	return;

}

edge e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,ll v)

{

	e[++edgenum] = (edge){b,lin[a],v};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],v};lin[b] = edgenum;

	return;

}

ll d[MAXN],d_[MAXN];

bool vis[MAXN];

int par[MAXN];

ll len[MAXN];

#define fi first

#define se second

#define mp make_pair

vector< pair<int,ll> > T[MAXN];

namespace HEAP

{

	struct node

	{

		int lc,rc,id,d;

		ll val,tag;

	}t[MAXM << 1];

	int ptr = 0;

	int createnode(int id,ll val)

	{

		int k = ++ptr;

		t[k].val = val;t[k].id = id;

		return k;

	}

	int root[MAXN];

	#define INF 0x3f3f3f3f3f3f3f3f

	void addtag(int rt,ll tag)

	{

		t[rt].val += tag;t[rt].tag += tag;

		return;

	}

	void pushdown(int rt)

	{

		if(t[rt].tag == 0)return;

		if(t[rt].lc)addtag(t[rt].lc,t[rt].tag);

		if(t[rt].rc)addtag(t[rt].rc,t[rt].tag);

		t[rt].tag = 0;

		return;

	}

	int merge(int x,int y)

	{

		if(x == 0 || y == 0)return x + y;

		if(t[x].val > t[y].val)swap(x,y);

		pushdown(x);

		t[x].rc = merge(t[x].rc,y);

		if(t[t[x].lc].d < t[t[x].rc].d)swap(t[x].lc,t[x].rc);

		t[x].d = t[t[x].rc].d + 1;

		return x;

	}

	void pop(int &rt)

	{

		pushdown(rt);

		rt = merge(t[rt].lc,t[rt].rc);

		return;

	}

}

bool son[MAXN];

int rnk[MAXN],tot = 0,siz[MAXN];

bool in(int id,int rt)

{

	if(rnk[id] == 0)return false;

	if(rnk[rt] <= rnk[id] && rnk[id] <= rnk[rt] + siz[rt] - 1)return true;

	return false;

}

void dfs(int k)

{

	rnk[k] = ++tot;siz[k] = 1;

	using namespace HEAP;

	for(vector< pair<int,ll> >::iterator it = T[k].begin();it != T[k].end();++it)son[it -> fi] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == par[k] || son[e[i].to])continue;

		root[k] = merge(root[k],createnode(e[i].to,d[e[i].to] + e[i].v));

	}

	for(vector< pair<int,ll> >::iterator it = T[k].begin();it != T[k].end();++it)son[it -> fi] = false;

	for(vector< pair<int,ll> >::iterator it = T[k].begin();it != T[k].end();++it)

	{

		dfs(it -> fi);

		addtag(root[it -> fi],it -> se);

		root[k] = merge(root[k],root[it -> fi]);

		siz[k] += siz[it -> fi];

	}

	while(root[k] != 0 && in(t[root[k]].id,k))pop(root[k]);

	if(root[k] != 0)d_[k] = t[root[k]].val;

	else d_[k] = INF;

	return;

}

ll f[MAXN];

int main()

{

	freopen("door.in","r",stdin);

	freopen("door.out","w",stdout);

	scanf("%d%d%d%d",&n,&m,&st,&ed);

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		a = rd();b = rd();c = rd();

		vadd(b,a,c);add(a,b,c);

	}

	memset(d,0x3f,sizeof(d));

	d[ed] = 0;

	priority_queue< pair<ll,int> > q;q.push(make_pair(0,ed));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(vis[k])continue;vis[k] = true;

		for(int i = vlin[k];i != 0;i = ve[i].nxt)

		{

			if(d[ve[i].to] > d[k] + ve[i].v)

			{

				par[ve[i].to] = k;len[ve[i].to] = ve[i].v;

				d[ve[i].to] = d[k] + ve[i].v;

				q.push(make_pair(-d[ve[i].to],ve[i].to));

			}

		}

	}

	for(int i = 1;i <= n;++i)if(i != ed)T[par[i]].push_back(mp(i,len[i]));

	dfs(ed);

	memset(f,0x3f,sizeof(f));

	f[ed] = 0;

	q.push(mp(0,ed));

	memset(vis,false,sizeof(vis));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(vis[k])continue;vis[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(f[e[i].to] > max(f[k] + e[i].v,(k == par[e[i].to] ? d_[e[i].to] : d[e[i].to])))

			{

				f[e[i].to] = max(f[k] + e[i].v,(k == par[e[i].to] ? d_[e[i].to] : d[e[i].to]));

				q.push(mp(-f[e[i].to],e[i].to));

			}

		}

	}

	if(f[st] < INF / 2)cout << f[st] << endl;

	else cout << -1 << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}