正解是LCT诶
然而我是懒boy不想写LCT（貌似也不怎么会打了）
写一下非正解SPFA：也是按A排序，不断加边，然后按B为权值跑SPFA
虽然复杂度并不是很正确的样子但是能过
|
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 |
// <3669.cpp> - 07/19/16 16:02:46 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=50010; const int MAXM=200010; const int INF=1e9; struct edge{ int u,v,a,b; bool operator <(const edge y) const{return a<y.a;} }e[MAXM]; int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM]; inline void add(int x,int y,int z){ next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=z; next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=z; } int dis[MAXN]; bool in[MAXN]; queue <int> q; int main(){ int n=gi(),m=gi(); for(int i=1;i<=m;i++)e[i].u=gi(),e[i].v=gi(),e[i].a=gi(),e[i].b=gi(); sort(e+1,e+m+1); for(int i=2;i<=n;i++)dis[i]=INF; int ans=INF; for(int i=1;i<=m;i++){ add(e[i].u,e[i].v,e[i].b); q.push(e[i].u);in[e[i].u]=1; q.push(e[i].v);in[e[i].v]=1; if(e[i].b==e[i+1].b)continue; while(!q.empty()){ int now=q.front();q.pop();in[now]=0; for(int i=b[now];i;i=next[i]){ if(max(dis[now],val[i])>=dis[to[i]])continue; dis[to[i]]=max(dis[now],val[i]); if(in[to[i]])continue; q.push(to[i]); in[to[i]]=1; } } ans=min(ans,dis[n]+e[i].a); } printf("%d",ans==INF?-1:ans); return 0; } |
说点什么