[NOI2014]魔法森林

[NOI2014]魔法森林

题目

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

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

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

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

INPUT

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

OUTPUT

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

SAMPLE

INPUT

4 5

1 2 19 1

2 3 8 12

2 4 12 15

1 3 17 8

3 4 1 17

OUTPUT

32

EXPLAIN

如果小E走路径$1 ightarrow 2 ightarrow 4$，需要携带$19+15=34$个守护精灵

如果小E走路径$1 ightarrow 3 ightarrow 4$，需要携带$17+17=34$个守护精灵

如果小E走路径$1 ightarrow 2 ightarrow 3 ightarrow 4$，需要携带$19+17=36$个守护精灵

如果小E走路径$1 ightarrow 3 ightarrow 2 ightarrow 4$，需要携带$17+15=32$个守护精灵

综上所述，小E最少需要携带32个守护精灵

解题报告

这题1A还被怀疑，我玩个鬼，要是不练1A能力，我考试咋玩啊

这题是个很简单的spfa，首先我们看，每条边有两个值，那么我们显然不能一起考虑，所以我们想，能否先确定一个值，然后用该值去确定另一个值，从而得到最优解？

显然可以。

我们可以先以a为关键字从小到大的枚举，让每一条边的a值都做一次最小的a值，将所有小于等于a的边加入图中，跑SPFA，找出在该条件下到n所需的b值，不断更新ans，直到最终更新出最优解

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<queue>
  6 using namespace std;
  7 inline int read(){
  8     int sum(0);
  9     char ch(getchar());
 10     for(;ch<'0'||ch>'9';ch=getchar());
 11     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
 12     return sum;
 13 }
 14 struct line{
 15     int s,e,a,b;
 16     friend bool operator<(const line &a,const line &b){
 17         return a.a<b.a;
 18     }
 19 }l[100005];
 20 int ttt;
 21 struct edge{
 22     int e,w;
 23     edge *n;
 24     edge():e(0),w(0),n(NULL){}
 25 }a[100005];
 26 int tot;
 27 edge *pre[50005];
 28 bool vis[50005];
 29 int dis[50005];
 30 struct node{
 31     int id;
 32     friend bool operator<(const node &a,const node &b){
 33         return dis[a.id]>dis[b.id];
 34     }
 35 }tmp,now;
 36 priority_queue<node>q;
 37 inline void insert(int s,int e,int w){
 38     a[++tot].e=e;
 39     a[tot].w=w;
 40     a[tot].n=pre[s];
 41     pre[s]=&a[tot];
 42 }
 43 inline void add(int s,int e,int a,int b){
 44     l[++ttt].s=s;
 45     l[ttt].e=e;
 46     l[ttt].a=a;
 47     l[ttt].b=b;
 48 }
 49 inline void spfa(){
 50     int id;
 51     while(!q.empty()){
 52         now=q.top();
 53         q.pop();
 54         id=now.id;
 55         vis[id]=0;
 56         for(edge *i=pre[id];i;i=i->n){
 57             int e(i->e),w(i->w),tp(max(dis[id],w));
 58             if(dis[e]>tp){
 59                 dis[e]=tp;
 60                 if(!vis[e]){
 61                     vis[e]=1;
 62                     tmp.id=e;
 63                     q.push(tmp);
 64                 }
 65             }
 66         }
 67     }
 68 }
 69 int n,m;
 70 inline int gg(){
 71     freopen("magicalforest.in","r",stdin);
 72     freopen("magicalforest.out","w",stdout);
 73     memset(dis,0x7f,sizeof(dis));
 74     int inf(dis[0]);
 75     n=read(),m=read();
 76     int ans(inf);
 77     for(int i=1;i<=m;i++){
 78         int x(read()),y(read()),z(read()),w(read());
 79         add(x,y,z,w);
 80     }
 81     sort(l+1,l+m+1);
 82     dis[1]=0,vis[1]=1;
 83     tmp.id=1;
 84     q.push(tmp);
 85     for(int i=1;i<=m;i++){
 86         int op(l[i].a);
 87         if(op>=ans)
 88             break;
 89         int j;
 90         for(j=i;j<=m;j++)
 91             if(l[j].a==op){
 92                 int s(l[j].s),e(l[j].e),b(l[j].b);
 93                 insert(s,e,b),insert(e,s,b);
 94                 if(!vis[s]){
 95                     vis[s]=1;
 96                     tmp.id=s;
 97                     q.push(tmp);
 98                 }
 99                 if(!vis[e]){
100                     vis[e]=1;
101                     tmp.id=e;
102                     q.push(tmp);
103                 }
104             }
105             else
106                 break;
107         spfa();
108         ans=min(ans,dis[n]+op);
109         i=j-1;
110     }
111     if(ans==inf)
112         puts("-1");
113     else
114         printf("%d",ans);
115 }
116 int K(gg());
117 int main(){;}

View Code

在COGS上rk1，然后在hzoj上T了= =，结果一调，邻接表开小了= =

我。。。