样例已过，其他全部输出afk求调qaq

Atri_Lobato @ 2024-11-12 11:33:02

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define Pair pair<ull,int>
#define ull unsigned long long 
using namespace std;
int n,m;
ull b;
int fee[10004];
int head[10005];
struct Edge
{
    int nxt,to;
    ull len;
}edge[100005];
int tot=0;
void add(int from,int to,ull len)
{
    tot++;
    edge[tot].len=len;
    edge[tot].nxt=head[from];
    edge[tot].to=to;
    head[from]=to;
}
ull dis[10005];
bool vis[10005];
priority_queue<Pair,vector<Pair>,greater<Pair> >q;
bool check(int maxf)
{
    for(int i=1;i<=n;i++)
    dis[i]=-1;
    memset(vis,0,sizeof(vis));
    while(q.empty()==0)
    q.pop();
    dis[1]=0;
    q.push(make_pair(0,1));
    while(q.empty()==0)
    {
        int now=q.top().second;
        q.pop();
        if(vis[now])
        continue;
        vis[now]=1;
        if(dis[now]>b)
        return 0;
        else if(now==n)
        return 1;
        for(int i=head[now];i;i=edge[i].nxt)
        {
            int np=edge[i].to;
            if(fee[np]>maxf)
            continue;
            if(vis[np])
            continue;
            if(dis[now]+edge[i].len<dis[np])
            {
                dis[np]=dis[now]+edge[i].len;
                q.push(make_pair(dis[np],np));
            }
        }
    }
    if(dis[n]<=b)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int main()
{
    int maxn=0;
    scanf("%d%d%llu",&n,&m,&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&fee[i]);
        maxn=max(maxn,fee[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        ull z;
        scanf("%d%d%llu",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    int l=fee[1],r=maxn;
    bool flag=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
        {
            flag=1;
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    if(flag)
    cout<<r+1;
    else
    cout<<"AFK";
    return 0;
}

by zxw1234567 @ 2024-11-12 12:23:54

@Atri_Lobato

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <cstring>

using namespace std;

int heap[20000], heap_size;//堆和堆的大小
int d[10005], d_heap[10005];//d记录起点到各个点的距离，d_heap记录d值在堆中对应位置
int city[10005];//各城市路费
int n, C, b;//点数，边数，总血量

void exchange(int &a, int &b)//交换
{
    int t = a;
    a = b;
    b = t;
}

int left(int i)//二叉堆的左结点
{
    return 2 * i;
}
int right(int i)//右节点
{
    return 2 * i + 1;
}
int parent(int i)//祖先节点
{
    return i / 2;
}

void heapify(int i)//维护堆的性质，假定左右子堆是符合性质的，处理根节点
{
    int l, r, m;
    l = left(i);
    r = right(i);
    if (l <= heap_size&&d[heap[i]] > d[heap[l]])
        m = l;
    else
        m = i;

    if (r <= heap_size&&d[heap[r]] < d[heap[m]])
        m = r;
    if (m != i)
    {//将根，左，右中最大的与根交换
        exchange(d_heap[heap[i]], d_heap[heap[m]]);//d_heap也要同时交换
        exchange(heap[m], heap[i]);
        heapify(m);//递归维护到符合性质为止
    }
}

void build_heap()//从无序数组中建堆
{
    heap_size = n;

    for (int i = heap_size / 2; i >= 1; i--)//堆的后半部分只有一个元素，符合条件，
    {                                       //无需维护
        heapify(i);
    }
}

void key_decrease(int i, int key)//缩小堆中某元素对应值并维护堆的性质
{
    d[heap[i]] = key;

    while (i > 1 && d[heap[i]] < d[heap[parent(i)]])
    {
        exchange(d_heap[heap[i]], d_heap[heap[parent(i)]]);
        exchange(heap[i], heap[parent(i)]);
        i = parent(i);
    }
}

void heap_insert(int i, int key)//增加元素，可用于实现另一种优化方式，
{                               //但这里没用到
    heap_size++;
    heap[heap_size] = i;
    key_decrease(heap_size, key);
}

int heap_extract_min()//提取堆中最小元素，输出且删除
{
    int min = heap[1];

    heap[1] = heap[heap_size];
    d_heap[heap[heap_size]] = 1;
    heap_size--;
    heapify(1);
    return min;
}

struct node {//邻接链表的节点
    int aim;
    int cost;
    node *next;
};

node *head[10005];//邻接链表的表头，每个城市对应一个

void add(node *&head, int aim, int cost)//向链表中添加一条边
{
    if (head == NULL)//需特判表首为空的情况
    {
        head = new(node);
        head->next = NULL;
        head->aim = aim;
        head->cost = cost;
    }
    else//在表首添加节点
    {
        node *p = new(node);
        p->aim = aim;
        p->cost = cost;
        p->next = head;
        head = p;
    }
}

void set()//初始化d值和heap，d_heap的值
{
    int i;

    for (i = 0; i < 10005; i++)
    {
        d[i] = 1000000005;
        heap[i] = i;
        d_heap[i] = i;
    }
    d[1] = 0;//起点距离为0
}

void relax(int u, node *p)//对边进行松弛操作，缩小上界
{
    if (d[p->aim] > d[u] + p->cost)
    {
        key_decrease(d_heap[p->aim], d[u] + p->cost);
    }
}

bool findway(int max)//这里是主要算法，dijkstral
{                    //判断最大值为max时是否可行
    set();
    build_heap();//初始化并建堆

    for (int i = 1; i <= n; i++)
    {
        int k = heap_extract_min();//取堆中最小元素

        node *p = head[k];
        while (p != NULL)//依次松弛邻接表中对应边
        {
            if (city[p->aim] <= max)//判断
                relax(k, p);
            p = p->next;
        }
    }

    if (d[n] >= b)//如果最小消耗大于等于血量，寻路失败
        return false;
    return true;
}

int main()
{
    int i, max = 0;
    int u, v, c;

    scanf("%d %d %d", &n, &C, &b);

    for (i = 1; i <= n; i++)
    {
        scanf("%d", &city[i]);
        if (city[i] > max)
            max = city[i];
    }
    max = max + 2;//输入并记录最大值，以缩小二分查找范围

    for (i = 0; i < C; i++)//记录边
    {
        scanf("%d %d %d", &u, &v, &c);
        add(head[u], v, c);//无向图，记录两遍
        add(head[v], u, c);
    }

    int l = city[1] - 1;
    int r = max;//二分范围

    while (1)//标准的二分查找
    {
        if (l + 1 == r)
            break;

        int mid = (l + r) / 2;
        if (findway(mid) == true)
            r = mid;
        else
            l = mid;
    }

    if (r > max - 2)//r大于max-2说明无法到达目标
        printf("AFK");
    else
        printf("%d", r);//输出答案

    system("pause");
    return 0;
}

by Atri_Lobato @ 2024-11-12 14:23:39

@zxw1234567 谢谢手打堆dalao 但是我就是自己比较题解代码没找到错才求助的喵呜qaq

by _HCl_ @ 2024-11-12 14:28:25

@Atri_Lobato 你前向星寸图写错了。

head[from]=to;

应为

head[from]=tot;

by Atri_Lobato @ 2024-11-12 15:00:32

@HCl ！！！！！！！！我是小丑了喵呀....

by 方块鼠 @ 2024-11-19 19:17:47

抓猫