Description：

给出一个 $N$ 个点 $M$ 条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点 $1$ 到点 $N$ 的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权。

$N\le100000$ $M\le200000$

Solution：

差分建图。

将每条边拆成两个新点，它们之间边权为原边权，并且两个点分属于原边的两端点。

对于同一个点的新点，将它们按原边权排序，边权小的新点向大的新点连长为原边权之差的边，大的点向小的点连长为 $0$ 的边。这样如果走的下一条边比之前大，那么会补上与差值相同的代价， 而下一条边比之前小，则答案不变。这样我们发现实际上这样建图除了起点别的点的代价都已计算好，于是原点向所有属于一号点的新点连边权为原边权的边，所有属于 $n$ 号点的新点向汇点连边权为 $0$ 的边，新图中点数为 $2m+ 2$ ，边数为 $6m−2n+ 2$ ， $Dijkstra$ 求最短路即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

#define MAXM 200010

struct edge1

{

	int to,v,id;

};

vector<edge1> g[MAXN];

bool cmp_e(edge1 x,edge1 y){return x.v < y.v;}

struct edge

{

	int to,nxt,v;

}e[MAXM << 3];

int edgenum = 0;

int lin[MAXM << 1] = {0};

inline void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

inline int get(edge1 k,int p){if(k.to < p)return k.id * 2;else return k.id * 2 - 1;}

long long d[MAXM << 1];

bool v[MAXM << 1];

int main()

{

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

	int a,b,c;

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

	{

		scanf("%d%d%d",&a,&b,&c);

		g[a].push_back((edge1){b,c,i});

		g[b].push_back((edge1){a,c,i});

		add(i * 2 - 1,i * 2,c);

		add(i * 2,i * 2 - 1,c);

	}

	for(int k = 1;k <= n;++k)

	{

		sort(g[k].begin(),g[k].end(),cmp_e);

		for(int i = 1;i < g[k].size();++i)

		{

			add(get(g[k][i],k),get(g[k][i - 1],k),0);

			add(get(g[k][i - 1],k),get(g[k][i],k),g[k][i].v - g[k][i - 1].v);

		}

	}

	int s = m * 2 + 1,t = s + 1;

	for(int i = 0;i < g[1].size();++i)

	{

		add(s,get(g[1][i],1),g[1][i].v);

	}

	for(int i = 0;i < g[n].size();++i)

	{

		add(get(g[n][i],n),t,0);

	}

	priority_queue< pair<long long,int> > q;

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

	memset(v,0,sizeof(v));

	d[s] = 0;

	q.push(make_pair(0,s));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();//cout << k << endl;

		if(v[k])continue;

		v[k] = true;

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

		{

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

			{

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

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

			}

		}

	}

	printf("%lld\n",d[t]);

	return 0;

}