洛谷P1462 通往奥格瑞玛的道路 题解
题目链接：
P1462 通往奥格瑞玛的道路
题意
：在艾泽拉斯，有
nn
n
个城市。编号为
1,
2
,
3
,
…
,
n
1,2,3,\ldots,n
1
,
2
,
3
,
…
,
n
。城市之间有
mm
m
条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。
假设
11
1
为暴风城，
nn
n
为奥格瑞玛，而他的血量最多为
bb
b
，出发时他的血量是满的。歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。
本题的数据是真的水，而且也没说清楚
b
b
b
最后可不可以为
0
0
0
，瞎搞的做法都能写 81pts qwq
看到最大值最小，首先可以想到二分
事实上，由于我们不清楚血量和最小值究竟有何关系（没关系），也只能用二分
注：二分的是这个最小值
在二分了一个值后，我们把伤害看作边权，然后跑个最短路，找一下最少伤害的路径，判断一下能不能到达终点即可
细节还是有点多的 qwq
懒得讲了看代码吧
Dijkstra
关于
SPFA
，它死了
实测（C++14 O2）SPFA 755ms，dijkstra 208ms
代码如下
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gc() getchar()
#define pc(a) putchar(a)
#define INF 0x3f3f3f3f3f3f3f3f
#define MAXN (int)(1e4+5)
template<typename T>void read(T &k)
{
char ch=gc(); T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n,m,b,l,r;
struct Edge
{
int u,v,w,next;
}e[MAXN*10];
struct node
{
int u,dis;
bool operator<(const node &o)const
{return dis>o.dis;}
};
int head[MAXN],pos=1,a[MAXN],t[MAXN],d[MAXN],vis[MAXN];
void addEdge(int u,int v,int w)
{
e[pos]={u,v,w,head[u]};
head[u]=pos++;
}
priority_queue<node> q;
int dijkstra(int bd)
{
if(bd<a[1]||bd<a[n])return 0;
memset(d,0x3f,sizeof(d));
q.push({1,0});d[1]=0;
for(int i=1; i<=n; i++)
vis[i]=a[i]>bd;
while(!q.empty())
{
int u=q.top().u;q.pop();
if(vis[u])
continue;
vis[u]=1;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(d[v]>d[u]+e[i].w)
{
d[v]=d[u]+e[i].w;
if(!vis[v])
q.push({v,d[v]});
}
}
}
return d[n]<b;
}
signed main()
{
read(n);read(m);read(b);
for(int i=1; i<=n; i++)
read(a[i]),t[i]=a[i];
for(int i=1,u,v,w; i<=m; i++)
{
read(u);read(v);read(w);
addEdge(u,v,w);addEdge(v,u,w);
}
sort(t+1,t+1+n);l=1;r=n;
if(!dijkstra(t[n]))return puts("AFK"),0;
while(l<r)
{
int mid=(l+r)>>1;
if(dijkstra(t[mid]))r=mid;
else l=mid+1;
}
write(t[l]);pc('\n');
return 0;
}
SPFA
好吧我知道有写SPFA的
贴下代码吧…
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gc() getchar()
#define pc(a) putchar(a)
#define INF 0x3f3f3f3f3f3f3f3f
#define MAXN (int)(1e4+5)
template<typename T>void read(T &k)
{
char ch=gc(); T x=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{
if(k<0){k=-k;pc('-');}
if(k>9)write(k/10);
pc(k%10+'0');
}
int n,m,b,l,r;
struct Edge
{
int u,v,w,next;
}e[MAXN*10];
int head[MAXN],pos=1,a[MAXN],t[MAXN],d[MAXN],vis[MAXN];
void addEdge(int u,int v,int w)
{
e[pos]={u,v,w,head[u]};
head[u]=pos++;
}
queue<int> q;
int spfa(int bd)
{
if(bd<a[1]||bd<a[n])return 0;
memset(d,0x3f,sizeof(d));
q.push(1);d[1]=0;vis[1]=1;
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u]; i; i=e[i].next)
{
int v=e[i].v;
if(d[v]>d[u]+e[i].w&&a[v]<=bd)
{
d[v]=d[u]+e[i].w;
if(!vis[v])
q.push(v),vis[v]=1;
}
}
}
return d[n]<b;
}
signed main()
{
read(n);read(m);read(b);
for(int i=1; i<=n; i++)
read(a[i]),t[i]=a[i];
for(int i=1,u,v,w; i<=m; i++)
{
read(u);read(v);read(w);
addEdge(u,v,w);addEdge(v,u,w);
}
sort(t+1,t+1+n);l=1;r=n;
if(!spfa(t[n]))return puts("AFK"),0;
while(l<r)
{
int mid=(l+r)>>1;
if(spfa(t[mid]))r=mid;
else l=mid+1;
}
write(t[l]);pc('\n');
return 0;
}
转载请说明出处