lp2387 NOI2014 魔法森林

这一题据说是LCT维护边权的题目。但是我们观察一下感觉可以用动态加边SPFA来跑这道题。 具体来说，对于每一条加进来的边，我们知道，并不是整张图都因为这条边而改变。这条边会改变的有且仅有图的一部分。 因此，我们不妨将所有边按照a的大小排序，然后将b节点作为关键字，跑动态加边SPFA。 然后答案对dis[n]+e[i].a去min即可。这是因为如果它没有影响原来的最短路，那么选择这条边的a肯定不会更优；如果更新了，那么就必须要选择这条边的a。 复杂度大概是松松松，构造了菊花套菊花也没有卡掉，就假装能过吧…求大佬证明。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
const int N=50005;
const int INF=0x3f3f3f3f;
struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
struct data{
	int u;int v;int a;int b;
	inline bool operator<(const data &B){
		return a^B.a?a<B.a:b<B.b;
	}
}ed[100005];
int h[N],et=0;
inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W){
	Eadd(U,V,W),Eadd(V,U,W);
}
int dis[N];
bool vis[N];
queue<int> q;
inline void SPFA(int s1,int s2){
	vis[s1]=vis[s2]=1;
	q.push(s1),q.push(s2);
	int p;
	while(!q.empty()){
		p=q.front();q.pop();
		for(int i=h[p];i;i=e[i].nxt){
			if(Max(dis[p],e[i].w)<dis[e[i].v]){
				dis[e[i].v]=Max(dis[p],e[i].w);
				if(!vis[e[i].v]){
					vis[e[i].v]=1;
					q.push(e[i].v);
				}
			}
		}
		vis[p]=0;
	}
}
int n,m;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;++i){
		dis[i]=INF;
	}
	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+1+m);
	int ans=INF;
	for(int i=1;i<=m;++i){
		add(ed[i].u,ed[i].v,ed[i].b);
		SPFA(ed[i].u,ed[i].v);
		ans=Min(ans,dis[n]+ed[i].a);
	}
	printf("%d\n",ans<INF?ans:-1);
}
int main(){
	init();
	return 0;
}