题解
首先求一个最短路图出来，最短路图就是这条边在最短路上就保留，否则就不保留，注意最短路图是一个有向图，一条边被保留的条件是
dis(S,u) + val(u,v) = dis(v,T)我们需要求两遍最短路
然后我们发现就相当于在最短路图上走一段，然后走一段非0的部分
我们把旧图保留，在上面连一些边权为0的有向边，从U到V求一遍最短路，由于最短路图是有向的，我们再从V到U求一遍最短路
然而……WA了？
我们发现我们最短路图上下来之后，可能会又走到最短路图上，但是同时选中两条路径是不可能的，我们希望的是在最短路上走一段，下来，并且再也不回到最短路图上
这样我们考虑分层图，设置三个状态，第一个状态是没有走到最短路图上，第二个状态是走到了最短路图上，第三个状态是走下来
所以要写两个dij，感觉代码还是十分的不优美，但是思路比较巧妙？
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#include <queue>
//#define ivorysi
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mo 974711
#define MAXN 100005
#define MAXM 200005
#define eps 1e-3
#define RG register
#define calc(x) __builtin_popcount(x)
#define pLI pair<int64,int>
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,M,S,T,U,V;
struct Edge {
int u,v;int64 c;
}C[MAXM];
struct Edge_link {
struct node {
int to,next;int64 val;
}E[MAXM * 4];
int head[MAXN],sumE;
void add(int u,int v,int64 c) {
E[++sumE].to = v;
E[sumE].next = head[u];
E[sumE].val = c;
head[u] = sumE;
}
}MK[2];
priority_queue<pLI > Q;
int64 dis[3][MAXN];
bool vis[MAXN * 3];
void dijkstra(int64 *D,int id,int s) {
for(int i = 1 ; i <= N ; ++i) D[i] = 1e18;
memset(vis,0,sizeof(vis));
D[s] = 0;
while(!Q.empty()) Q.pop();
Q.push(mp(0,s));
while(!Q.empty()) {
pLI now = Q.top();Q.pop();
now.fi = -now.fi;
if(vis[now.se]) continue;
vis[now.se] = 1;
D[now.se] = now.fi;
for(int i = MK[id].head[now.se] ; i ; i = MK[id].E[i].next) {
int v = MK[id].E[i].to;
if(!vis[v] && D[now.se] + MK[id].E[i].val < D[v]) {
D[v] = D[now.se] + MK[id].E[i].val;
Q.push(mp(-D[v],v));
}
}
}
}
void Another(int id,int s) {
for(int i = 1 ; i <= N ; ++i) {
for(int j = 0 ; j < 3 ; ++j) dis[j][i] = 1e18;
}
dis[0][s] = 0;dis[1][s] = 0;dis[2][s] = 0;
memset(vis,0,sizeof(vis));
while(!Q.empty()) Q.pop();
Q.push(mp(0,s)),Q.push(mp(0,N + s)),Q.push(mp(0,2 * N + s));
while(!Q.empty()) {
pLI now = Q.top();Q.pop();
now.fi = -now.fi;
if(vis[now.se]) continue;
int t = (now.se - 1) / N,u = now.se - t * N;
dis[t][u] = now.fi;
vis[now.se] = 1;
for(int i = MK[id].head[u] ; i ; i = MK[id].E[i].next) {
int v = MK[id].E[i].to;
if(MK[id].E[i].val == 0 && t != 1) continue;
if(t == 2) {
if(MK[id].E[i].val != 0) {
if(dis[2][v] > dis[2][u] + MK[id].E[i].val) {
dis[2][v] = dis[2][u] + MK[id].E[i].val;
Q.push(mp(-dis[2][v],2 * N + v));
}
}
}
if(t == 1) {
if(MK[id].E[i].val == 0 && dis[1][v] > dis[1][u]) {
dis[1][v] = dis[1][u];
Q.push(mp(-dis[1][v],N + v));
}
else if(dis[2][v] > dis[1][u] + MK[id].E[i].val){
dis[2][v] = dis[1][u] + MK[id].E[i].val;
Q.push(mp(-dis[2][v],2 * N + v));
}
}
if(t == 0) {
if(MK[id].E[i].val != 0) {
if(dis[0][v] > dis[0][u] + MK[id].E[i].val) {
dis[0][v] = dis[0][u] + MK[id].E[i].val;
Q.push(mp(-dis[0][v],v));
}
if(dis[1][v] > dis[0][u] + MK[id].E[i].val) {
dis[1][v] = dis[0][u] + MK[id].E[i].val;
Q.push(mp(-dis[1][v],v + N));
}
}
}
}
}
}
void Solve() {
read(N);read(M);
read(S);read(T);read(U);read(V);
int u,v;int64 c;
for(int i = 1 ; i <= M ; ++i) {
read(u);read(v);read(c);
C[i] = (Edge){u,v,c};
MK[0].add(u,v,c);MK[0].add(v,u,c);
}
dijkstra(dis[0],0,S);
dijkstra(dis[1],0,T);
for(int i = 1 ; i <= M ; ++i) {
if(dis[0][C[i].u] + C[i].c + dis[1][C[i].v] == dis[0][T]) MK[1].add(C[i].u,C[i].v,0);
else if(dis[0][C[i].v] + C[i].c + dis[1][C[i].u] == dis[0][T]) MK[1].add(C[i].v,C[i].u,0);
MK[1].add(C[i].u,C[i].v,C[i].c),MK[1].add(C[i].v,C[i].u,C[i].c);
}
Another(1,U);
int64 ans = min(min(dis[0][V],dis[1][V]),dis[2][V]);
Another(1,V);
ans = min(ans,min(dis[0][U],dis[1][U]));
ans = min(ans,dis[2][U]);
out(ans);enter;
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}