题目
思路
看完了题，这不就是最短路吗？
怀着对SPFA的热爱之心去码了一遍，一遍AC！！！（这竟然没卡SPFA）
这里就是在松弛之后，向队列加点时加一点判断，看看此时这点的雪是否太厚而被困住，如果不会就加入队列，否则不加。
代码
话不多说，代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
}
这题就是这样，谢谢浏览。