这是怎么回事???

P1462 通往奥格瑞玛的道路

与世无争 @ 2020-01-09 23:38:29

下数据自测第六个点是过的,Luogu不给我过,怎么办

#pragma GCC optimize(2)
#include<queue>
#include<cstdio>
#include<vector>
using namespace std;
inline int read() {
    register int n=0;
    register char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
    return n;
}
inline int max(register int q,register int p) {
    return (q>p)?q:p;
}
inline int min(register int q,register int p) {
    return (q<p)?q:p;
}
struct Node {
    int x,b;
    bool operator < (const Node &xxoo) const {
        b>xxoo.b;
    }
} t,y;
priority_queue <Node> q;
const int N=10005;
int n,m,p,a[N],from,to,kkk,l=1e9,r,mid,f[N];
bool visit[N],flag,pd,ans;
vector <int> v[N],s[N];
int main() {
    n=read();
    m=read();
    p=read();
    for (register int i=1; i<=n; i++) {
        a[i]=read();
        l=min(l,a[i]);
        r=max(r,a[i]);
    }
    while (m--) {
        from=read();
        to=read();
        kkk=read();
        v[from].push_back(to);
        s[from].push_back(kkk);
        v[to].push_back(from);
        s[to].push_back(kkk);
    }
    while (l<=r) {
        mid=(l+r)>>1;
        for (register int i=1; i<=n; i++) {
            visit[i]=0;
            f[i]=1e9;
        }
        flag=0;
        t.x=1;
        t.b=0;
        q.push(t);
        f[1]=0;
        while (!q.empty()) {
            t=q.top();
            q.pop();
            from=t.x;
            visit[from]=1;
            pd=0;
            for (register int i=0; i<v[from].size(); i++) {
                to=v[from][i];
                kkk=s[from][i];
                if (a[to]<=mid&&kkk+t.b<f[to]&&kkk+t.b<p&&(!visit[to])) {
                    if (to==n) {
                        pd=1;
                        break;
                    }
                    f[to]=kkk+t.b;
                    y.x=to;
                    y.b=f[to];
                    q.push(y);
                }
            }
            if (pd) {
                flag=1;
                break;
            }
        }
        while (!q.empty()) q.pop();
        if (flag) {
            r=mid-1;
            ans=1;
        } else l=mid+1;
    }
    if (ans) printf("%d\n",l);
    else printf("AFK\n");
    return 0;
}
//By与世无争

by 与世无争 @ 2020-01-09 23:38:42

@苍空的蓝耀


by 与世无争 @ 2020-01-09 23:38:58

@空气树


by 与世无争 @ 2020-01-09 23:39:33

@QwQ永动鸭


by 与世无争 @ 2020-01-09 23:40:47

@famvics


by 春待ち @ 2020-01-09 23:42:24

仔细检查一下会不会是输出格式的问题?


by pocafup @ 2020-01-10 00:04:10

麻烦给数据


by HaveFun @ 2020-01-10 07:00:52

@与世无争 您要先确定做法是对的(


by 与世无争 @ 2020-01-10 18:31:56

@QwQ永动鸭 是对的


by 风羽跃 @ 2020-03-01 16:36:19

用洛谷的IDE测数据


|