一个暴力的做法是把边看成点，之间的边权为两边的较大权值，最短路即可。但这样显然会被菊花图之类的卡掉。

　　考虑优化建图。将边拆成两个有向边，同样化边为点。原图中同一条边在新图中的两个点之间连边权为原边权的边。对于原图同一点的出边按权值从小到大排序，权值相邻的由小到大连边权为差值的边，由大到小连边权为0的边。这样就完成了取max的操作。加上超源超汇即可。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 100010#define M 200010int n,m,p[M<<1],t=0;long long d[M<<1];bool flag[M<<1];struct data{ int to,nxt,len;}edge[M<<3];struct data3{ int x,y,z,i;}e[M<<1];struct data2{ int x;long long d; bool operator <(const data2&a) const { return d>a.d; }};priority_queue
            
              q;void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}void dijkstra(){ while (!q.empty()) q.pop(); memset(d,42,sizeof(d));d[0]=0;q.push((data2){ 0,0}); memset(flag,0,sizeof(flag)); for (int i=1;i<=m*2+1;i++) { while (!q.empty()&&flag[q.top().x]) q.pop(); if (q.empty()) break; data2 v=q.top();q.pop(); flag[v.x]=1; for (int j=p[v.x];j;j=edge[j].nxt) if (v.d+edge[j].len
             
              i;j--) addedge(e[j].i,e[j-1].i,0); i=t; } for (int i=1;i<=m*2;i++) { if (e[i].x==1) addedge(0,e[i].i,e[i].z); if (e[i].y==n) addedge(e[i].i,m*2+1,e[i].z); } dijkstra(); cout<