WA了5个点

P1462 通往奥格瑞玛的道路

LiveZoom @ 2020-04-02 21:53:01

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 10005;
const int M = 50005;

int read() {
    int p = 0, sign = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')sign = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        p = (p << 1) + (p << 3) + (ch ^ 48);
        ch = getchar();
    }
    return p * sign;
}

struct edge {
    int to;
    int w;
    int pre;
}e[M << 1];

struct node {
    int id;
    int dis;
    node (int _id, int _dis) {
        id = _id;
        dis = _dis;
    }
    friend bool operator < (const node &n1, const node &n2) {
        return n1.dis > n2.dis;
    }
};

int n, m, b;
int f[N];

int cnt, tail[N];

int dis[N];
bool vis[N];

void addEdge (int u, int v, int w) {
    cnt++;
    e[cnt].to = v;
    e[cnt].w = w;
    e[cnt].pre = tail[u];
    tail[u] = cnt;
}

bool check (int k) {
    memset(vis, false, sizeof(vis));
    priority_queue<node> q;
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
    }
    dis[1] = 0;
    q.push(node(1, 0));
    while (!q.empty()) {
        node nowtop = q.top();
        q.pop();
        int id = nowtop.id;
        if (vis[id]) continue;
        vis[id] = true;
        for (int i = tail[id]; i; i = e[i].pre) {
            int nextid = e[i].to;
            if (f[nextid] <= k && dis[nextid] > dis[id] + e[i].w) {
                dis[nextid] = dis[id] + e[i].w;
                q.push(node(nextid, dis[nextid]));
            }
        }
    }
    if (dis[n] >= k) return false;
    else return true;
}

signed main() {
    n = read(), m = read(), b = read();
    for (int i = 1; i <= n; i++) {
        f[i] = read();
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        int w;
        u = read(), v = read(), w = read();
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    int L = -1, R = INF + 1;
    while (L + 1 < R) {
        int mid = (L + R) / 2;
        if (check(mid)) R = mid;
        else L = mid;   
    }
    if (R == INF + 1) cout << "AFK" << endl;
    else cout << R << endl;
    return 0;
}

蒟蒻求助

by gongyr @ 2020-04-02 22:00:55

大佬%%%

by raincity @ 2020-04-03 16:20:59

@liu_winner

可以对拍：

#include<bits/stdc++.h>
#define N 10100
#define M 100100
#define INF 0x3f3f3f3f
using namespace std;

struct node{
    int dis,id;
    bool friend operator <(const node &a,const node &b){
        return a.dis>b.dis;
    }
}a[N];
struct edge{
    int u,v,w;
    int nxt;
}e[M];
int f[N],head[N],dis[N];
int n,m,b,l=INF,r=-INF;
bool vis[N];
priority_queue<node> q;

void addedge(int u,int v,int w,int id){
    e[id].u=u;e[id].v=v;e[id].w=w;
    e[id].nxt=head[u];
    head[u]=id;
}
void init(){
    int u,v,w;
    scanf("%d%d%d",&n,&m,&b);
    for(int i=1;i<=n;i++){
        scanf("%d",f+i);
        l=min(l,f[i]);r=max(r,f[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w,i);addedge(v,u,w,m+i);
    }
}
void Dijkstra(int cost){
    memset(vis,false,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    node from;
    from.dis=0;from.id=1;q.push(from);
    dis[1]=0;
    while(!q.empty()){
        node t=q.top();
        q.pop();
        vis[t.id]=true;
        for(int i=head[t.id];i!=0;i=e[i].nxt)
            if(vis[e[i].v]==false&&f[e[i].v]<=cost&&dis[e[i].u]+e[i].w<dis[e[i].v]){
                dis[e[i].v]=dis[e[i].u]+e[i].w;
                node t;
                t.dis=dis[e[i].v];t.id=e[i].v;
                q.push(t);
            }
    }
}
void solve(){
    init();
    int ans=INF,mid;
    while(l<=r){
        mid=(l+r)>>1;
        Dijkstra(mid);
        if(dis[n]<b) ans=mid,r=mid-1;
        else l=mid+1;
    }
    if(ans==INF) puts("AFK");
    else printf("%d\n",ans);
}
int main(){
    solve();
    return 0;
}

by LiveZoom @ 2020-04-03 17:33:53

@Calvincheng1231 我改出来了

by raincity @ 2020-04-03 21:00:58

哦好的

|