学姐每次出门逛街都要带恰好M元钱, 不过她今天却忘记带钱包了.
可怜的doc只好自己凑钱给学姐, 但是他口袋里只有一元钱.
好在doc的N位朋友们都特别有钱, 他们答应与doc作一些交换.
其中第i位朋友说:
如果doc有不少于Ri元钱,
doc可以把手上所有的钱都给这位朋友,
并从这位朋友手中换回Vi元钱,
但是这次交换会浪费Ti的时间.
doc希望可以在最短的时间内换到M元钱(其实是可以大于M的, 因为doc可以存私房钱呢), 否则学姐会生气的!

输入格式

输出格式

样例输入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.

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 #include<queue>  9 #include<map> 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<b.val; 33 } 34 map<int,int>mp; 35 int id=0; 36 int T; 37 int n,m; 38 int u[mxn],v[mxn],d[mxn]; 39 queue<int>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 }