NOI 2014 魔法森林

前言

我觉得我的博客需要加上标签…
这本来想用来练LCT的…

题目

题目描述

为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图，节点标号为 1,2,3,…,n，边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点，隐士则住在 n 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在 1 号节点住着两种守护精灵：A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。

只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边 ei 包含两个权值 ai 与 bi 。若身上携带的 A 型守护精灵个数不少于 ai ，且 B 型守护精灵个数不少于 bi ，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小 E 发起攻击，他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的个数与 B 型守护精灵的个数之和。

输入输出格式

输入格式：

输入文件的第 1 行包含两个整数 n,m，表示无向图共有 n 个节点，m 条边。接下来 m 行，第i+ 1 行包含 4 个正整数 Xi,Yi,ai,bi，描述第i条无向边。其中Xi与 Yi为该边两个端点的标号，ai 与 bi 的含义如题所述。注意数据中可能包含重边与自环。

输出格式：

输出一行一个整数：如果小 E 可以成功拜访到隐士，输出小 E 最少需要携带的守护精灵的总个数；如果无论如何小 E 都无法拜访到隐士，输出“-1”（不含引号）。

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

3 1 
1 2 1 1

输出样例#2：

-1

说明

解释1

如果小 E 走路径 1→2→4，需要携带 19+15=34 个守护精灵；如果小 E 走路径 1→3→4，需要携带 17+17=34 个守护精灵；如果小 E 走路径 1→2→3→4，需要携带 19+17=36 个守护精灵；如果小 E 走路径 1→3→2→4，需要携带 17+15=32 个守护精灵。综上所述，小 E 最少需要携带 32 个守护精灵。

解释2

小 E 无法从 1 号节点到达 3 号节点，故输出-1。

数据范围

100%的数据：n<=50000,m<=100000, 0<=a,b<=50000

解题

我们有两种方法来解这道题…
还有这道题数据范围是一张带洛谷水印的图…随意手打…

spfa单源最短路

思路

首先跑Spfa的时间复杂度无法保证

AC代码1028ms

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cctype>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
#define xep(i,x) for(re i=head[x];i;i=e[i].nxt)
#define INF 0x3f3f3f3f

using namespace std;

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

const int N=50010;
const int M=100010;
int n,m,head[2*M],cnt=0,ans=INF;
int vis[N],sum[N];
queue < int > q;
struct edge{
    int nxt,to,val1,val2;
}e[2*M];
struct line{
    int x,y,a,b;
    inline bool operator <(const line &rhy)const{
        return a<rhy.a;
    }
}l[M];

inline void add(int x,int y,int v1,int v2){
    e[++cnt].nxt=head[x];e[cnt].to=y;
    e[cnt].val1=v1;e[cnt].val2=v2;head[x]=cnt;
}

inline void spfa(int x,int y){
    vis[x]=1;vis[y]=1;
    q.push(x);q.push(y);
    while(!q.empty()){
        int u=q.front();vis[u]=0;q.pop();
        xep(i,u){
            int v=e[i].to;
            if(max(e[i].val2,sum[u])<sum[v]){
                sum[v]=max(e[i].val2,sum[u]);
                if(!vis[v]) vis[v]=1,q.push(v);
            }
        }
    }
}

int main(){
    n=read();m=read();
    rep(i,1,m){
        int x,y,z,p;
        x=read();y=read();z=read();p=read();
        l[i].a=z;l[i].b=p;l[i].x=x;l[i].y=y;
    }
    sort(l+1,l+1+m);
    memset(sum,INF,sizeof(sum));
    sum[1]=0;vis[1]=1;q.push(1);
    rep(i,1,m){
        add(l[i].x,l[i].y,l[i].a,l[i].b);
        add(l[i].y,l[i].x,l[i].a,l[i].b);
        spfa(l[i].x,l[i].y);
        ans=min(ans,sum[n]+l[i].a);
    }
    if(ans==INF) puts("-1");
    else printf("%d\n",ans);
    return 0;
}

（PS：洛谷数据水…

前言

题目