题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3669
由于有两个关键字，不能正常跑spfa，所以我们想办法将一个关键字消除
先把每个边按照第一个关键字从小到大排序，然后一个一个的插入到图中，每插入一条边从这条边的两个端点跑一边spfa
这时候的spfa中的边权只有第二关键字，因为我们认为当前会经过新的边，所以第一关键字最大的一定是当前这个。
每次的答案就是 当前边的第一关键字+spfa的答案，最后取一个min就好了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include<bits/stdc++.h> #define MAXN 50050 #define MAXM 100010 #define inf INT_MAX/2 #define pb push_back using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int to,len; node(){} node(int a,int b){to=a,len=b;} }; struct node1{ int from,to,w1,w2; friend bool operator < (node1 a,node1 b){ return a.w1<b.w1; } }e[MAXM]; int n,m,ans; int dis[MAXN]; bool vis[MAXN]; pr pa; vector<node>v[MAXN]; queue<int>q; inline void spfa(){ while(!q.empty()){ int now=q.front(); q.pop(); for(int i=0; i<v[now].size(); i++){ int to=v[now][i].to; int num=v[now][i].len; if(dis[to]>max(dis[now],num)){ dis[to]=max(dis[now],num); if(!vis[to])q.push(to),vis[to]=true; } } vis[now]=false; } } int main(){ n=rd(),m=rd(); for(int i=1; i<=m; i++){ e[i].from=rd(); e[i].to=rd(); e[i].w1=rd(); e[i].w2=rd(); } sort(e+1,e+m+1); ans=inf; fill(dis+1,dis+n+1,inf); q.push(1); dis[1]=0; vis[1]=true; for(int i=1; i<=m; i++){ v[e[i].from].pb(node(e[i].to,e[i].w2)); v[e[i].to].pb(node(e[i].from,e[i].w2)); q.push(e[i].from),vis[e[i].from]=true; q.push(e[i].to),vis[e[i].to]=true; spfa(); ans=min(ans,e[i].w1+dis[n]); } if(ans==inf)ans=-1; printf("%d\n",ans); return 0; } |