洛谷——P3946 ことりのおやつ（小鸟的点心）

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

题目太长，请去链接里看吧

注意细节：特判终点（即使困住又能怎样，到达就好了），特判高度

#include<bits/stdc++.h>

#define N 10101010
#define inf 0x7fffffff
using namespace std;

int tot,head[N];
struct nodE{
    int to,next,w;
}e[N];

void add(int u,int v,int w){
    e[++tot].to=v,e[tot].next=head[u],head[u]=tot,e[tot].w=w;
}

struct node{
    int to,d;
    friend bool operator < (node A,node B){
        return A.d>B.d;
    }
};
struct nxde{
    int h,l;
}P[N];
priority_queue<node>Q;

bool vis[N];

int n,m,s,t,g,q,d[N];

void spfa(){
    fill(d+1,d+1+n,inf);
    Q.push((node){s,0});d[s]=0,vis[s]=1;
    while(!Q.empty()){
        int u=Q.top().to;Q.pop();vis[u]=0;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if(d[v]>d[u]+e[i].w){
                if(P[v].h+(d[u]+e[i].w)*q>P[v].l&&v!=t) continue;
                d[v]=d[u]+e[i].w;
                if(!vis[v]) vis[v]=1,Q.push((node){v,d[v]});
            }
        }
    }
}

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",&P[i].h,&P[i].l);
    
    for(int u,v,w,i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    
    spfa();
    
    if(d[t]>g) printf("wtnap wa kotori no oyatsu desu!
");
    else printf("%d
",d[t]);
    
    return 0;
}