Vijos1901 学姐的钱包-白红宇

Vijos1901 学姐的钱包

阅读量：6251 次

发布时间：2019-06-22

本文共 3109 字，大约阅读时间需要 10 分钟。

描述

学姐每次出门逛街都要带恰好M元钱, 不过她今天却忘记带钱包了.

可怜的doc只好自己凑钱给学姐, 但是他口袋里只有一元钱.

好在doc的N位朋友们都特别有钱, 他们答应与doc作一些交换.

其中第i位朋友说:

如果doc有不少于Ri元钱,

doc可以把手上所有的钱都给这位朋友,

并从这位朋友手中换回Vi元钱,

但是这次交换会浪费Ti的时间.

doc希望可以在最短的时间内换到M元钱(其实是可以大于M的, 因为doc可以存私房钱呢), 否则学姐会生气的!

格式

输入格式

输入数据第一行给定T, 表示总的询问次数.

对于每一次询问, 第一行给出两个整数N和M.

之后N行, 每一行给出三个整数Vi, Ri和Ti. (保证Ri<=Vi).

输出格式

对于每一次询问, 首先输出询问的编号, 参见样例输出.

之后输出最小需要的时间, 如果不可能完成目标, 则输出-1.

样例1

样例输入1

35 95 1 110 4 108 1 1011 6 17 3 84 52 1 13 2 14 3 18 4 13 105 1 38 2 510 9 2

样例输出1

Case #1: 10Case #2: 4Case #3: -1

限制

对于40%的数据

N <= 1500.

对于100%的数据

T <= 5

1 <= N <= 100000.

1 <= M <= 1000000000.

1 <= Ri <= Vi <= 1000000000.

1 <= Ti <= 1000000000.

看到这题，觉得可以用类似差分约束的办法建图跑SPFA，然而写起来有些无力。

查了一发题解，看别人是怎么写的，第一眼看到的是隔壁阿当学长的线段树DP，第二眼看到的是隔壁OrionRigel的神奇SPFA……害怕。

既然知道SPFA可行了，就乱搞试试看，真的搞出来了

将每一个可以到达的价值离散化（这里用了巨慢的map，最大一个点跑了1000ms），依据题中的转化关系连边。之后从大价值向小价值连一条权为0的有向边（回溯），跑SPFA即可。

1 /*by SilverN*/  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
             7 #include
           
             8 #include
            
              9 #include
              10 #define LL long long 11 using namespace std; 12 const int mxn=400010; 13 int read(){ 14 int x=0,f=1;char ch=getchar(); 15 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 16 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 17 return x*f; 18 } 19 struct edge{ 20 int v,nxt,dis; 21 }e[mxn<<2]; 22 int hd[mxn],mct=0; 23 void add_edge(int u,int v,int dis){ 24 e[++mct].v=v;e[mct].dis=dis;e[mct].nxt=hd[u];hd[u]=mct; 25 return; 26 } 27 // 28 struct node{ 29 int val,id; 30 }a[mxn]; 31 int cmp(const node a,const node b){ 32 return a.val
              
               mp; 35 int id=0; 36 int T; 37 int n,m; 38 int u[mxn],v[mxn],d[mxn]; 39 queue
               
                q; 40 bool inq[mxn]; 41 LL dis[mxn];LL INF; 42 void SPFA(int st){ 43 memset(dis,0x3f,sizeof dis); 44 INF=dis[0]; 45 while(!q.empty()) q.pop(); 46 q.push(st); 47 inq[st]=1; 48 dis[st]=0; 49 while(!q.empty()){ 50 int u=q.front();q.pop(); 51 for(int i=hd[u];i;i=e[i].nxt){ 52 int v=e[i].v; 53 if(dis[v]>dis[u]+e[i].dis){ 54 dis[v]=dis[u]+e[i].dis; 55 if(!inq[v]){ 56 inq[v]=1; 57 q.push(v); 58 } 59 } 60 } 61 inq[u]=0; 62 } 63 return; 64 } 65 void init(){ 66 memset(e,0,sizeof e); 67 memset(hd,0,sizeof hd); 68 memset(inq,0,sizeof inq); 69 mct=id=0; 70 mp.clear(); 71 return; 72 } 73 74 int main(){ 75 freopen("10.in","r",stdin); 76 T=read(); 77 int i,j; 78 int cas=0; 79 while(T--){ 80 init(); 81 n=read();m=read(); 82 mp[m]=++id; 83 a[id].val=m;a[id].id=id; 84 for(i=1;i<=n;i++){ 85 u[i]=read();v[i]=read();d[i]=read(); 86 if(u[i]>m)u[i]=m; 87 if(v[i]>m)v[i]=m; 88 if(!mp[u[i]]){ 89 mp[u[i]]=++id; 90 a[id].id=id; 91 a[id].val=u[i]; 92 } 93 if(!mp[v[i]]){ 94 mp[v[i]]=++id; 95 a[id].id=id; 96 a[id].val=v[i]; 97 } 98 add_edge(mp[v[i]],mp[u[i]],d[i]); 99 }100 sort(a+1,a+id+1,cmp);101 for(i=2;i<=id;i++){102 add_edge(a[i].id,a[i-1].id,0);103 }104 LL ans;105 if(a[1].val==1){106 SPFA(a[1].id);ans=dis[mp[m]];107 }108 else ans=-1;109 if(ans>=INF)ans=-1;110 printf("Case #%d: %lld\n",++cas,ans);111 }112 return 0;113 }

转载于:https://www.cnblogs.com/SilverNebula/p/6055630.html

你可能感兴趣的文章