这道题…正解是LCT（然而我不会），所以把我的动点SPFA发上来混一波23333，对于这个问题，应该是类似瓶颈生成树？？对此，我们可以很好想出一个贪心+最短路策略，我们先把每一条边按照A的权值排序，然后枚举每一条边，跑一遍对于B的最短路，之后用新加入的边的A权值更新一下到终点的答案，然后….然后就完事了！一道考数据结构的题就这样水过23333 SPFA时间复杂度蜜汁不科学啊啊啊啊啊 代码如下
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,top=0,maxa=0,ans=1e9;
int dis[100005],f[100005];
bool inq[100005];
struct edge{int x,y,a,b;
}p[200005];
inline bool cmp(edge x,edge y){if(x.a==y.a) return x.b<y.b;return x.a<y.a;
}
struct ddf{int nex,to,b;
}a[200005];
inline void add(int x,int y,int b){a[++top]=(ddf){f[x],y,b};f[x]=top;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i].a,&p[i].b);sort(p+1,p+m+1,cmp);for(int i=2;i<=n;i++) dis[i]=1e9;for(int i=1;i<=m;i++){add(p[i].x,p[i].y,p[i].b);add(p[i].y,p[i].x,p[i].b);queue<int> q1;q1.push(p[i].x),q1.push(p[i].y);inq[p[i].x]=1,inq[p[i].y]=1;while(!q1.empty()){int u=q1.front(); for(int i=f[u];i;i=a[i].nex){int v=a[i].to;if(max(a[i].b,dis[u])<dis[v]){dis[v]=max(a[i].b,dis[u]);if(!inq[v]) inq[v]=1,q1.push(v);}}q1.pop();inq[u]=0;}if(p[i].a+dis[n]<ans) ans=p[i].a+dis[n];}if(ans==1e9) printf("-1");else printf("%d",ans);return 0;
}