搜索
提供一种不一样的做法。
我在写这个题的时候刚刚学了二分和搜索 还不会最短路，就把这个题当做二分题写了。可能是数据比较水吧。首先看到最小值最大或者最大值最小，我们的第一直觉就是二分答案。
我们二分最大值，我们只走那些小于等于二分的答案的路，如果我们能够走到终点，就说明我们设置的条件比较弱，我们就可以减小二分的答案，当我们走不到终点的时候，就说明我们二分的条件比较严，我们就应该调大我们二分的答案，一直这样下去我们就能找到一个比较精确的值，当这个条件精确到唯一的一个值的时候，我们就二分到了我们要的答案。
二分答案很重要的就是check()函数了，很多大佬都是写的最短路（dijkstral/spfa），将掉血量看成路的长度，看看符合条件的掉血量是否符合条件，然后再调整mid值，继续二分。二分的复杂度为(O(log(n))),然后再乘上最短路的时间复杂度，就是整体的时间复杂度。但是我写这个题的时候还不会写最短路，之好写了搜索，但可能是数据比较水，被我水过了，当然，我后续会补上关于最短路的题解。
以下就是我的早期代码，可能存在的问题比较多，倘若有什么问题，还望大家不吝赐教，指出我的错误。
最后献上我丑陋的代码
#include<iostream>
#include<cstdio>
using namespace std;
struct bian
{
int to,nt,dis;
}e[100001];
int f[10001],head[10001],tot,ans;
bool flag=0;
int n,m,b,x,y,z;
void add(int from,int to,int dis)
{
e[++tot].to=to;
e[tot].dis=dis;
e[tot].nt=head[from];
head[from]=tot;
}
void check(int fr,int l,int x,int q)
{
if(f[1]>q||f[n]>q) {flag=0;return;}
if(fr==n) {flag=1;return;}
for(int i=head[fr];i;i=e[i].nt)
{
if(f[e[i].to]<=q&&x-e[i].dis>0&&e[i].to!=l)
{
check(e[i].to,fr,x-e[i].dis,q);
}
if(flag==1)return;
}
}
int main()
{
cin>>n>>m>>b;
for(int i=1;i<=n;++i)scanf("%d",&f[i]);
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
int l=0,r=2147483646;
check(1,0,b,2147483646);
if(flag==0)
{
cout<<"AFK";
return 0;
}
while(l<=r)
{
flag=0;
int mid=(l+r)>>1;
check(1,0,b,mid);
if(flag==1)
{
r=mid-1;
ans=mid;
}
else l=mid+1;
}
cout<<ans;
return 0;
}
update
已经补上关于最短路的题解(SPFA)
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
const int N=10010;
struct bian
{
int to,nt,dis;
}e[100001];
int n,m,b,x,y,z,tot,ans;
int f[N],head[N];
long long dis[N];
bool vis[N];
void add(int from,int to,int dis)
{
e[++tot].to=to;
e[tot].dis=dis;
e[tot].nt=head[from];
head[from]=tot;
}
bool check(int mid)
{
if(f[1]>mid||f[n]>mid)return 0;
memset(dis,0x3f,sizeof(dis));
queue<int>q;
q.push(1);
vis[1]=1;dis[1]=0;
while(!q.empty())
{
int x=q.front();
q.pop();vis[x]=0;
for(int i=head[x];i;i=e[i].nt)
{
if(f[e[i].to]>mid)continue;
if(dis[e[i].to]>dis[x]+e[i].dis)
{
dis[e[i].to]=dis[x]+e[i].dis;
if(!vis[e[i].to])
{
q.push(e[i].to);
vis[e[i].to]=1;
}
}
}
}
return dis[n]<b;
}
int main()
{
cin>>n>>m>>b;
for(int i=1;i<=n;++i)scanf("%d",&f[i]);
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
int l=0,r=2147483646;
if(!check(2147483646))
{
cout<<"AFK";
return 0;
}
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
r=mid-1;
ans=mid;
}
else l=mid+1;
}
cout<<ans;
return 0;
}
效率高了一倍,珍爱生命，远离 乱搞