ことりのおやつ（小鸟的点心）

题目

点这里

思路

看完了题，这不就是最短路吗？

怀着对SPFA的热爱之心去码了一遍，一遍AC！！！（这竟然没卡SPFA）

这里就是在松弛之后，向队列加点时加一点判断，看看此时这点的雪是否太厚而被困住，如果不会就加入队列，否则不加。

代码

话不多说，代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=500001;
int n,m,s,t,g,q,h[maxn],l[maxn],cnt,head[maxn],dis[maxn];
bool vis[maxn];
struct node{
	int nxt,to,w;
}edge[maxn<<2];
void add(int x,int y,int w){
	edge[++cnt]=(node){head[x],y,w};
	head[x]=cnt;
}
void SPFA(){
	memset(dis,63,sizeof(dis));//离出发点一开始都设为一个很大的数
	dis[s]=0; vis[s]=1;//SPFA基本操作
	queue<int>que; que.push(s);
	while(que.size()){
		int d=que.front();que.pop();vis[d]=0;//别忘了标记去掉
		for(int i=head[d];i;i=edge[i].nxt){
			int y=edge[i].to;
			if(dis[y]>dis[d]+edge[i].w){//松弛操作
				dis[y]=dis[d]+edge[i].w;
				if(!vis[y]&&l[y]>=h[y]+dis[y]*q) que.push(y),vis[y]=1;
                //就是在这里加判断，从出发开始到这里的这段时间中下的雪加上原来的雪是否大于限制
			}
		}
	}
}
int main(){
	scanf("%d%d%d%d%d%d",&n,&m,&s,&t,&g,&q);
	for(int i=1;i<=n;i++) scanf("%d%d",&h[i],&l[i]);
	int x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z),add(y,x,z);//注意这里是双向边
	}
	SPFA();
	if(dis[t]<=g) cout<<dis[t]<<endl;//如题意，输出
	else cout<<"wtnap wa kotori no oyatsu desu!"<<endl;
	return 0;
}

这题就是这样，谢谢浏览。