点击这里查看原题
把所有边以a为第一关键字，b为第二关键字进行排序，依次加边，每加一条边做一次SPFA，看能否缩小答案。
/* User:Small Language:C++ Problem No.:3669 */ #include<bits/stdc++.h> #define ll long long #define inf 999999999 using namespace std; const int M=1e5+5; int n,ans,tot,fir[M>>1],m,dis[M>>1]; bool vis[M>>1]; queue<int> q; struct no{ int u,v,a,b; bool operator<(const no y)const{ return a==y.a?b<y.b:a<y.a; } }ed[M]; struct edge{ int v,b,nex; }e[M<<1]; void add(int u,int v,int b){ e[++tot]=(edge){v,b,fir[u]}; fir[u]=tot; } int main(){ freopen("data.in","r",stdin);// ios::sync_with_stdio(0); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d%d",&ed[i].u,&ed[i].v,&ed[i].a,&ed[i].b); sort(ed+1,ed+m+1); ans=inf; memset(dis,127,sizeof(dis)); dis[1]=0; for(int i=1;i<=m;i++){ add(ed[i].u,ed[i].v,ed[i].b); add(ed[i].v,ed[i].u,ed[i].b); if(!vis[ed[i].u]){ vis[ed[i].u]=1; q.push(ed[i].u); } if(!vis[ed[i].v]){ vis[ed[i].v]=1; q.push(ed[i].v); } if(ed[i].a==ed[i-1].a&&ed[i].b==ed[i-1].b) continue; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int j=fir[u];j;j=e[j].nex){ int v=e[j].v; if(dis[v]>max(dis[u],e[j].b)){ dis[v]=max(dis[u],e[j].b); if(!vis[v]){ vis[v]=1; q.push(v); } } } } ans=min(ans,dis[n]+ed[i].a); } if(ans==inf) ans=-1; printf("%d\n",ans); return 0; }