【BZOJ3669】【NOI2014】魔法森林

正解是LCT诶

然而我是懒boy不想写LCT（貌似也不怎么会打了）

写一下非正解SPFA：也是按A排序，不断加边，然后按B为权值跑SPFA

虽然复杂度并不是很正确的样子但是能过

// <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;
}

// <3669.cpp> - 07/19/16 16:02:46

// This file is created by XuYike's black technology automatically.

// 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;

}

说点什么