题目描述
宝塔有nn层，A向一个dalao购买了魔法，可以从第xx层跳到第yy层，也可以从第yy层跳到xx层。但每种魔法都有诅咒和一个分值kk，每使用一次魔法，会用tt个单位的时间，也就会得到一个诅咒，如果你的诅咒数大于等于这个魔法的分值kk，那么这个魔法就不能使用了（在这之前魔法无限使用）。AA的初始诅咒值为-1。 AA被dalao强制使用了一次魔法（AA本身不会这个魔法），从第一层跳到了第pp层（pp可以是1）。望眼四周，空空如也，没有路。要到达遥远的第qq层，好像只能编程了吧。输出最少到达所需的时间。如果到天荒地老都到不了，输出“bao 0”（不包含单引号）。
感天动地的SPFA，在模板中改一点就行
要加上的就是每次出现能将时间更新到更优的也要进行扩展
但是为什么卡了我一个下午呢？
这道题的数据不知道有什么问题，会把read卡掉
一下午每次提交都会T四个点，找了标程对拍都没用，我只想说一句，出数据要走心呐！！！
下面给出代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } inline void write(long long x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } int n,m; int head[4000006]; int nxt[4000006]; int to[4000006]; long long v[4000006]; int u[4000006]; int total=0; inline void add(int x,int y,int z,int f){ to[++total]=y; v[total]=z; u[total]=f; nxt[total]=head[x]; head[x]=total; return ; } int p,e; long long dis[4000006]; int q[4000006],t[4000006],tm[4000006],l=0,r=0; long long inf=2147483646; inline void spfa(int x){ for(int i=1;i<=n;i++) dis[i]=inf; q[++r]=x; t[r]=0; dis[x]=0,tm[x]=0; while(l<r){ int h1=q[++l]; int h2=t[l]+1; for(register int e=head[h1];e;e=nxt[e]){ if((dis[to[e]]>dis[h1]+v[e]||tm[to[e]]>h2)&&h2<=u[e]){ if(dis[to[e]]>dis[h1]+v[e]){ dis[to[e]]=dis[h1]+v[e]; tm[to[e]]=h2; } q[++r]=to[e]; t[r]=h2; } } } return ; } int main(){ //n=rd(),m=rd(),p=rd(),e=rd(); n=rd(),m=rd(),p=rd(),e=rd(); for(register int i=1;i<=m;i++){ int x,y,z,f; cin>>x>>y>>z>>f; add(x,y,z,f),add(y,x,z,f); } spfa(p); if(dis[e]==inf) printf("bao 0"); else write(dis[e]); return 0; }