【Luogu P3946】ことりのおやつ

【Luogu P3946】题面见此


AC Code

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

struct pts {
    int h, l, max;
};
struct edges {
    int to, we;
    bool operator < (const edges &other) const {
        return we > other.we;
    }
};

int n, m, s, t, g, q;
int dis[MAXN], vis[MAXN];
pts pt[MAXN];
vector<edges> grp[MAXN];

void dij() {
    priority_queue<edges> que;
    for(int i = 1; i <= n; ++i) dis[i] = INF;
    dis[s] = 0;
    que.push((edges) {s, 0});
    while(!que.empty()) {
        edges k = que.top();
        que.pop();
        if(vis[k.to]) continue;
        vis[k.to] = 1;
        if(k.we >= pt[k.to].max) continue;
        for(int i = 0; i < grp[k.to].size(); ++i){
            if(dis[k.to] + grp[k.to][i].we < dis[grp[k.to][i].to]) {
                dis[grp[k.to][i].to] = dis[k.to] + grp[k.to][i].we;
                que.push((edges) {grp[k.to][i].to, grp[k.to][i].we + k.we});
            }
        }
    }
}

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", &pt[i].h, &pt[i].l);
        if(q != 0) pt[i].max = (pt[i].l - pt[i].h + q - 1) / q;
        else pt[i].max = INF + 1;
    }
    for(int i = 1; i <= m; ++i) {
        int arg1, arg2, arg3;
        scanf("%d%d%d" ,&arg1, &arg2, &arg3);
        grp[arg1].push_back((edges) {arg2, arg3});
        grp[arg2].push_back((edges) {arg1, arg3});
    }
    dij();
    if(dis[t] > g) printf("wtnap wa kotori no oyatsu desu!\n");
    else printf("%d\n", dis[t]);  
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注