BuXiangJuanLe @ 2018-10-30 14:46:11
跪求dalao挑错Orz,代码应该能看懂
#include<bits/stdc++.h>
#define maxn 10100
#define maxm 50100
using namespace std;
typedef long long ll;
int n, m, head[maxn], vis[maxn], cnt;
ll b, cost[maxn], a[maxn], l, r, mid, ans;
struct edge{
int to, nxt;
ll w;
}e[maxm<<1];
inline void add(int u, int v, ll d){
e[++cnt].to = v;
e[cnt].w = d;
e[cnt].nxt = head[u];
head[u] = cnt;
}
bool SPFA(ll lim){ //经过的城市最大不得超过lim
queue <int> q;
memset(vis, 0, sizeof(vis));
memset(cost, 0x7f, sizeof(cost));
cost[1] = 0;
q.push(1);
vis[1] = 1;
while(q.size()){
int u = q.front();
q.pop();
for(int i=head[u] ; i ; i=e[i].nxt){
int v = e[i].to;
ll d = e[i].w;
if(a[v] > lim) continue; //超过lim,不能走
if(cost[v] > cost[u] + d){
cost[v] = cost[u] + d;
if(!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
vis[u] = 0;
}
if(cost[n] < b) return true; //还可以进一步放宽限制
return false;
}
int main(){
scanf("%d%d%lld", &n, &m, &b);
for(int i=1 ; i<=n ; i++){
scanf("%lld", &a[i]);
r = max(r, a[i]);
}
l = max(a[1], a[n]), ++r;
for(int i=1 ; i<=m ; i++){
int x, y; ll z;
scanf("%d%d%lld", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
if(!SPFA(r)){
puts("AFK");
return 0;
}
while(l < r){
mid = (l + r)>>1;
if(SPFA(mid)) ans = mid, l = mid + 1; //放宽最大花费,让城市变多
else r = mid;
}
printf("%lld\n", ans);
return 0;
}
by AIRC @ 2018-10-30 14:47:35
先膜为敬%%%
by hhhhyq @ 2018-10-30 14:47:37
by RiverFun @ 2018-10-30 14:47:45
@Izayoi
我觉得你的这个二分有问题
by BuXiangJuanLe @ 2018-10-30 14:49:14
@Steve_braveman emm,是check出了问题还是边界的问题啊
by RiverFun @ 2018-10-30 14:51:29
@Izayoi
你这个二分操作好像查找的不是已有的最小的点权,而是最小点权
by RiverFun @ 2018-10-30 14:53:27
边界也定错了,r
应该是点权数
by BuXiangJuanLe @ 2018-10-30 15:01:57
@Steve_braveman emm谢谢dalao,我再看看
by BuXiangJuanLe @ 2018-10-30 16:30:41
@Steve_braveman 好像……只是我的二分写反了233
by RiverFun @ 2018-10-30 16:32:54
@Izayoi
。。。。。。那可能咱俩做法不一样