题目描述

这是2017年的冬天。(又到了白色相簿的季节2333)

滑完雪之后,ことり突然想吃点心啦!于是她去了甜品店。

日本的冬天经常下雪。不幸的是,今天也是这样,每秒钟雪的厚度会增加q毫米。

秋叶原共有n个地点,编号从1到n。每个地点在开始的时候的积雪高度为hi。

有m条双向道路连接这些地点,它们的长度分别为wi米。

雪太大,公共交通系统已经停摆了,所以ことり得走路回家。她走路的速度是1m/s。

为了方便地图的绘制,秋叶原的道路规划使得每条道路严格地连接两个不同的地点,并且不会有两条道路连接的地点相同。

每个地点都有一个极限雪高li,单位是毫米,如果到达这个地点的时候,这里的雪的高度高于li则会被困在这个点走不出去,无法成功地走到ことり家。

点心店这个地点的编号是s,ことり家的编号是t。

不考虑点心店和ことり家的雪。

ことり想在g秒内回到家吃点心,越快越好。如果在g秒之内,ことり无法到家,或者她被困在路上了,那么ことり会把wtnap变成她的点心( ・ 8 ・ )

输入格式

第1行6个整数,空格隔开,分别代表n,m,s,t,g,q。

以下n行,每行2个整数,空格隔开,分别表示这个地点的hi和li。

以下m行,每行3个整数,空格隔开,分别表示这条路连接的两个地点u, v和这条路的长度wi。

输出格式

输出1行1个整数,表示到达ことり家的最短用时。

如果wtnap变成了ことり的点心那么输出"wtnap wa kotori no oyatsu desu!"

输出时不含引号。

输入输出样例

输入 #1
2 1 1 2 10 1
1 10
3 10
1 2 6
输出 #1
6
输入 #2
5 6 2 5 10 1
1 10
1 10
1 10
1 10
1 10
1 5 9
1 3 9
2 4 1
2 5 9
3 4 1
3 5 6
输出 #2
8
输入 #3
5 6 2 5 10 1
1 10
1 10
10 10
1 10
1 10
1 5 9
1 3 9
2 4 1
2 5 11
3 4 1
3 5 6
输出 #3
wtnap wa kotori no oyatsu desu!

说明/提示

对于0%的数据,与样例一模一样;
对于40%的数据,q = 0。
对于上一行中50%的数据,所有wi < li。
对于100%的数据,1 ≤ s, t ≤ n; 0 ≤ g, q ≤ 10^9; 0 ≤ wi ≤ li ≤ 10^9。

 
题解:只是SPFA接近板子题目。QAQ
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
const string AFO="wtnap wa kotori no oyatsu desu!";
const int N=500005;
int n,m,s,t,g,qq;
int cnt,h[N],l[N],x,y,z;
int head[N],dis[N];
bool vis[N];
queue<int>q;
struct node{
    int to,next,val;
}e[N<<2];
void add(int u,int v,int va){
    e[++cnt].to=v;
    e[cnt].val=va;
    e[cnt].next=head[u];
    head[u]=cnt;
}

void SPFA(int s){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    vis[s]=1; dis[s]=0;
    q.push(s); int x,v;
    while(!q.empty()){
        x=q.front(); q.pop(); vis[x]=0;
        for(int i=head[x];i;i=e[i].next){
            v=e[i].to;
            if(dis[v]>dis[x]+e[i].val){
                dis[v]=dis[x]+e[i].val;
                if(!vis[v] && l[v]>=h[v]+dis[v]*qq)
                   { vis[v]=1; q.push(v); }
            }
        }
    }
}



int main(){
    scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&g,&qq);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&h[i],&l[i]);
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,z); add(y,x,z);
    }
    SPFA(s);
    if(dis[t]<g) printf("%d\n",dis[t]);
    else cout<<AFO<<endl;
    return 0;
}
01-07 18:47