Bianca_ @ 2018-09-07 19:00:28
我通过看题解分析懂了这道题到底想求什么 然而不知道该如何断句才能正确get到题目意思 跪求解释一下下
就是这句话：
他所经过的所有城市中最多的一次收取的费用的最小值是多少
by 夢·壹生所愛 @ 2018-09-07 19:11:58
是他经过的所有城市收费 中最大的收费 最小的一次 是多少
by Bianca_ @ 2018-09-07 19:22:05
那这篇题解中说道：
经过城市最多的一次 这次的费用最小值是多少
这句话是不对的吧挠头
by Arashi丶 @ 2018-09-07 19:36:35
显然不对啊.....
看了一眼血量的范围顿时觉得不可以dp
by 夢·壹生所愛 @ 2018-09-07 19:39:41
二分加dijkstra正解
by Bianca_ @ 2018-09-07 20:45:21
@lovelausanneforever 写了个dijkstra然而挂了 正想求助
by Bianca_ @ 2018-09-07 20:46:18
@Arashi丶 dijkstra写挂怎么破
by Bianca_ @ 2018-09-07 20:46:55
#include<iostream>
#include<cstdio>
#include<queue>
#define INF 0x7fffffff
using namespace std;
const int maxn=10100,maxm=50100;
struct node{
int num,key;
bool operator < (const node &a) const{
return key>a.key;
}
};
int n,m,b,cnt,ans;
int l,r;
int f[maxn],d[maxn],vis[maxn];
int g[maxn],nxt[maxm<<1],to[maxm<<1],c[maxm<<1];
inline void add(int u,int v,int w){
nxt[++cnt]=g[u];
g[u]=cnt;
to[cnt]=v;
c[cnt]=w;
}
inline bool judge(int maxx){
for(int i=1;i<=n;i++){
if(f[i]>maxx) vis[i]=1;
else vis[i]=0;
d[i]=INF;
}
d[1]=0;
priority_queue<node>q;
q.push((node){1,d[1]});
while(!q.empty()){
node x=q.top();q.pop();
int now=x.num;
if(vis[now]) continue;
vis[now]=1;
for(int o=g[now];o;o=nxt[o]){
int v=to[o],w=c[o];
if(d[v]>d[now]+w){
d[v]=d[now]+w;
q.push((node){v,d[v]});
}
}
}
if(d[n]>b) return 0;
return 1;
}
int main(){
scanf("%d%d%d",&n,&m,&b);
scanf("%d",&f[1]);l=r=f[1];
for(int i=2;i<=n;i++){
scanf("%d",&f[i]);
l=f[i]<l?f[i]:l;
r=f[i]>r?f[i]:r;
}
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
if(judge(INF)){
printf("AFK");
return 0;
}
while(l<=r){
int mid=(l+r)>>1;
if(judge(nid)){
r=mid-1;
ans=c[mid];
}
else l=mid+1;
}
printf("%d",ans);
return 0;
}by Arashi丶 @ 2018-09-07 20:53:24
那就写SPFA吧...这题数据好像不卡SPFA
by Arashi丶 @ 2018-09-07 20:57:07
很好奇你们最短路怎么挂的
by Bianca_ @ 2018-09-07 20:57:42
@Arashi丶 简单地说 就是过不了样例 我去试试spfa