求助!27分,实在不会了

P1462 通往奥格瑞玛的道路

BuXiangJuanLe @ 2018-10-30 14:46:11

跪求dalao挑错Orz,代码应该能看懂

#include<bits/stdc++.h>
#define maxn 10100 
#define maxm 50100 
using namespace std;
typedef long long ll;
int n, m, head[maxn], vis[maxn], cnt;
ll b, cost[maxn], a[maxn], l, r, mid, ans;

struct edge{
    int to, nxt;
    ll w;
}e[maxm<<1];

inline void add(int u, int v, ll d){
    e[++cnt].to = v;
    e[cnt].w = d;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

bool SPFA(ll lim){ //经过的城市最大不得超过lim 
    queue <int> q;
    memset(vis, 0, sizeof(vis));
    memset(cost, 0x7f, sizeof(cost));
    cost[1] = 0;
    q.push(1);
    vis[1] = 1;

    while(q.size()){
        int u = q.front();
        q.pop();
        for(int i=head[u] ; i ; i=e[i].nxt){
            int v = e[i].to;
            ll d = e[i].w;
            if(a[v] > lim) continue; //超过lim,不能走 
            if(cost[v] > cost[u] + d){
                cost[v] = cost[u] + d;
                if(!vis[v]){
                    q.push(v);
                    vis[v] = 1;
                }
            } 
        }
        vis[u] = 0;
    }

    if(cost[n] < b) return true; //还可以进一步放宽限制 
    return false;
}

int main(){
    scanf("%d%d%lld", &n, &m, &b);
    for(int i=1 ; i<=n ; i++){
        scanf("%lld", &a[i]);
        r = max(r, a[i]);
    }
    l = max(a[1], a[n]), ++r;

    for(int i=1 ; i<=m ; i++){
        int x, y; ll z;
        scanf("%d%d%lld", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }

    if(!SPFA(r)){
        puts("AFK");
        return 0;
    }

    while(l < r){
        mid = (l + r)>>1;
        if(SPFA(mid)) ans = mid, l = mid + 1; //放宽最大花费,让城市变多 
        else r = mid;
    }

    printf("%lld\n", ans);
    return 0;
}

by AIRC @ 2018-10-30 14:47:35

先膜为敬%%%


by hhhhyq @ 2018-10-30 14:47:37

其实楼主是妹子


by RiverFun @ 2018-10-30 14:47:45

@Izayoi

我觉得你的这个二分有问题


by BuXiangJuanLe @ 2018-10-30 14:49:14

@Steve_braveman emm,是check出了问题还是边界的问题啊


by RiverFun @ 2018-10-30 14:51:29

@Izayoi

你这个二分操作好像查找的不是已有的最小的点权,而是最小点权


by RiverFun @ 2018-10-30 14:53:27

边界也定错了,r应该是点权数


by BuXiangJuanLe @ 2018-10-30 15:01:57

@Steve_braveman emm谢谢dalao,我再看看


by BuXiangJuanLe @ 2018-10-30 16:30:41

@Steve_braveman 好像……只是我的二分写反了233


by RiverFun @ 2018-10-30 16:32:54

@Izayoi

。。。。。。那可能咱俩做法不一样


|