题目链接:
思路:
又是一道水题,很明显二分+最短路
而且这道题数据非常水,spfa有个小错误居然拿了91分还比正解快
我们二分金钱数,节点权值大于二分值的都不能走。二分中跑spfa,如果不能走到终点,即dis[n]>=b,则说明二分值偏小。
注意:
代码:
#include
#include
#include
#include
#include
#include
#include
#include
#define ri register int
#define ll long long
using namespace std;
const ll inf=9926081792;
const int maxn=10005;
const int maxm=50005;
ll g[maxn],dis[maxn];
int h[maxn],num_edge=0;
bool vis[maxn];
int n,m;
ll b;
struct Edge{
int ne,to;
ll dis;
}edge[maxm<<2];
inline void add_edge(int f,int t,ll dis){
edge[++num_edge].ne=h[f];
edge[num_edge].to=t;
edge[num_edge].dis=dis;
h[f]=num_edge;
}
template
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
inline int spfa(ll len){
deque
int u,v,c;
while(q.size())q.pop_front();
//memset(vis,0,sizeof(vis));
for(ri i=1;i<=n;i++){dis[i]=inf,vis[i]=0;}
dis[1]=0,vis[1]=1;
q.push_back(1);
while(!q.empty()){
u=q.front();q.pop_front();
for(ri i=h[u];i;i=edge[i].ne){
v=edge[i].to;
if((len-g[v]>=0)&&dis[v]>dis[u]+edge[i].dis){
dis[v]=dis[u]+edge[i].dis;
if(q.empty()){
if(!vis[v]){
vis[v]=1;
q.push_back(v);
}
}
c=q.front();
if(dis[v]>dis[c]){
if(!vis[v]){
vis[v]=1;
q.push_back(v);
}
}
else if(!vis[v]){
vis[v]=1;
q.push_front(v);
}
}
}
vis[u]=0;
}
if(dis[n]>=b)return 0;
return 1;
}
int main(){
ll l=1,r=n;
int u,v,c;
read(n),read(m),read(b);
for(ri i=1;i<=n;i++)read(g[i]);
for(ri i=1;i<=m;i++){
read(u),read(v),read(c);
add_edge(u,v,c);
add_edge(v,u,c);
}
if(!spfa(inf)){
puts("AFK");
return 0;
}
while(l
if(spfa(mid))r=mid;
else l=mid+1;
}
printf("%d",r);
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章