与世无争 @ 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测数据