关于H题,样例错了,却ac

#define first x
#define second y 
#include<bits/stdc++.h>
using namespace std;
      
typedef long long ll;
typedef unsigned long long ull;
typedef pair <ll , ll> pii;
const int N = 2e5 + 10,mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

ll h[N],e[N],w[N],ne[N],idx;
ll n,m,s,t,c;
ll num[N],dist[N],sum[N];
bool st[N];
ll minn = inf,maxn;

void add(int a,int b,int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

void dijkstra(int mid)
{
    memset(dist , -1 , sizeof dist);
    memset(st , 0 , sizeof st);
    dist[s] = 0;
    sum[s] = num[s];
    priority_queue <pii , vector<pii> , greater<pii> > heap;
    heap.push({dist[s] , s});

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int v = t.y;
        if(st[v])
        {
            continue;
        }
        st[v] = 1;

        for(int i = h[v] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            dist[j] = max(dist[j] , w[i]);
            sum[j] = sum[v] + num[j];
            if(dist[j] > mid || sum[j] > c)
            {
                continue;
            }else
            {
                heap.push({dist[j] , j});
            }
        }
    }
}

void work()
{
    cin>>n>>m>>s>>t>>c;
    memset(h , -1 , sizeof h);

    for(int i = 1 ; i <= n ; i++)
    {
        cin>>num[i];
    }

    while(m--)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        add(a , b , c);
        minn = min(minn , c);
        maxn = max(maxn , c);
    }

    ll l = minn,r = maxn;
    while(l < r)
    {
        ll mid = (l + r) >> 1;
        dijkstra(mid);
        if(dist[t] != -1)
        {
            r = mid;
        }else
        {
            l = mid + 1;
        }
    }

    cout<<r;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),cout.tie(0);

    work();
}

以上代码样例结果是3,但是提交却ac了,之所以输出是3是因为49和50行应该在判断完可以接受以后再更改,代码如下

#define first x
#define second y 
#include<bits/stdc++.h>
using namespace std;
      
typedef long long ll;
typedef unsigned long long ull;
typedef pair <ll , ll> pii;
const int N = 2e5 + 10,mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int h[N],e[N],w[N],ne[N],idx;
int n,m,s,t,c;
int num[N],dist[N],sum[N];
bool st[N];
int minn = inf,maxn;
void add(int a,int b,int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

void dijkstra(int mid)
{
    memset(dist , -1 , sizeof dist);
    memset(st , 0 , sizeof st);
    dist[s] = 0;
    sum[s] = num[s];
    priority_queue <pii , vector<pii> , greater<pii> > heap;
    heap.push({dist[s] , s});

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int v = t.y,dis = t.x;
        if(st[v])
        {
            continue;
        }
        st[v] = 1;

        for(int i = h[v] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            
            if(max(dist[j] , w[i]) > mid || sum[v] + num[j] > c)
            {
                continue;
            }else
            {	
				sum[j] = sum[v] + num[j];
				dist[j] = max(dist[j] , w[i]);
                heap.push({dist[j] , j});
            }
        }
    }
}

void work()
{
    cin>>n>>m>>s>>t>>c;
    memset(h , -1 , sizeof h);

    for(int i = 1 ; i <= n ; i++)
    {
        cin>>num[i];
    }

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a , b , c);
        minn = min(minn , c);
        maxn = max(maxn , c);
    }

    int l = minn,r = maxn;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        dijkstra(mid);
        if(dist[t] != -1)
        {
            r = mid;
        }else
        {
            l = mid + 1;
        }
    }

    cout<<r;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),cout.tie(0);

    work();
}



以上代码是可以过样例的,但是却wa了,想知道为什么

全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务