SkyLiYu @ 2019-03-13 08:23:09

- WA码

by SkyLiYu @ 2019-03-13 08:23:47

Ac码

#include <iostream>
#include <queue>

using namespace std;

const long long INF = 1e18;
struct Edges
{
    int to , next , key;
}edge[100010];
int first[10010] , cost[10010] , cnt = 0 , n;
long long dis[10010];
bool vis[10010];
queue <int> que;

void add(int a , int b , int c)
{
    edge[++cnt].to = b;
    edge[cnt].key = c;
    edge[cnt].next = first[a] , first[a] = cnt;
}

bool check(int lit , int hp)
{
    if(lit < cost[1]) return 0;
    que.push(1) , vis[1] = 1 , dis[1] = 0;
    for(int i = 2; i <= n; i++) dis[i] = INF;
    while(!que.empty())
    {
        int now = que.front();
        vis[now] = 0 , que.pop();
        for(int i = first[now]; i; i = edge[i].next)
        {
            int to = edge[i].to;
            if(cost[to] > lit) continue;
            if(dis[to] > (long long)(dis[now] + edge[i].key))
            {
                dis[to] = (long long)(dis[now] + edge[i].key);
                if(!vis[to]) vis[to] = 1 , que.push(to);
            }
        }
    }
    if(dis[n] <= (long long) hp) return 1;
    else return 0;
}

int main()
{
    int m , b , l = 1e9 , r = 0;
    cin >> n >> m >> b;
    for(int i = 1; i <= n; i++)
    {
        cin >> cost[i]; 
        r = max(r , cost[i]);
        l = min(l , cost[i]);
    }
    for(int i = 1; i <= m; i++)
    {
        int a , b , c;
        cin >> a >> b >> c;
        add(a , b , c) , add(b , a , c);
    }
    int ans =1e9;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(check(mid , b)) ans = mid , r = mid - 1;
        else l = mid + 1;
    }
    if(ans < 1e9) cout << ans << endl;
    else cout << "AFK" << endl;
    return 0;
}

by SkyLiYu @ 2019-03-13 08:24:18

WA码

    #include <iostream>
    #include <queue>
    #include <cstdio>

    using namespace std;

    struct Edges
    {
        int next , to;
        long long key;
    }edge[100010];
    long long first[10010] , dis[10010] , hp , cnt = 0 , date[10010] , n;
    bool vis[10010];
    queue <int> que;

    void add(int a , int b , int c)
    {
        edge[++cnt].to = b , edge[cnt].key = c;
        edge[cnt].next = first[a] , first[a] = cnt;
    }

    void spfa(int lit)
    {
        que.push(1);
        fill(dis , dis + n + 1 , 1e18);
        dis[1] = 0 , vis[1] = 1;
        while(!que.empty())
        {
            int now = que.front();
            que.pop() , vis[now] = 0;
            for(int i = first[now]; i; i = edge[i].next)
            {
                int to = edge[i].to;
                if(date[to] > lit) continue;
                if(dis[now] + edge[i].key < dis[to])
                {
                    dis[to] = dis[now] + edge[i].key;
                    if(!vis[to]) que.push(to) , vis[to] = 1;
                }
            }
        }
    }

    bool check(int now)
    {
        spfa(now);
        if(dis[n] <= hp) return 1;
        else return 0;
    }

    int main()
    {
        //freopen("test.in" , "r" , stdin);
        long long m , l , r = 0;
        cin >> n >> m >> hp;
        for(int i = 1; i <= n; i++)
        {
            cin >> date[i];
            r = max(r , date[i]);
        }
        l = max(date[1] , date[n]);
        for(int i = 1; i <= n; i++)
        {
            int a , b , c;
            cin >> a >> b >> c;
            add(a , b , c) , add(b , a , c);
        }
        long long ans = 1e18;
        while(l <= r)
        {
            long long mid = (l + r) / 2;
            if(check(mid)) ans = mid , r = mid - 1;
            else l = mid + 1;
        }
        if(ans < 1e18) cout << ans << endl;
        else cout << "AFK" << endl;
        return 0;
    }