SBBSBSBSBSB @ 2024-08-23 21:30:39
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
int read()
{
int sum = 0,fg = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-')fg = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
sum = sum * 10 + c - '0';
c = getchar();
}
return sum * fg;
}
const int Max = 10004;
int f[Max];
struct node
{
int y,ne;
int z;
}a[Max * 10];
int head[Max],sum = 0;
void add(int x,int y,int z)
{
a[++ sum].y = y;
a[sum].ne = head[x];
a[sum].z = z;
head[x] = sum;
}
struct point
{
int x;
int w;
bool operator < (const point xx) const
{
return xx.w < w;
}
};
int dis[Max];
bool use[Max];
priority_queue<point>q;
int n,m,hp;
bool check(int mid)
{
memset(dis,0x3f,sizeof(dis));
memset(use,false,sizeof(use));
dis[1] = 0;
q.push((point){1,0});
while(!q.empty())
{
int x = q.top().x;
q.pop();
if(use[x] == true)
continue;
use[x] = true;
for(register int i = head[x];i != 0;i = a[i].ne)
{
int awa = a[i].y;
if(dis[awa] > dis[x] + a[i].z && f[awa] <= mid)
{
dis[awa] = dis[x] + a[i].z;
if(use[awa] == false)
q.push((point){awa,dis[awa]});
}
}
}
if(dis[n] < hp)
return true;
return false;
}
signed main()
{
n = read(),m = read(),hp = read();
int r = 0;
for(register int i = 1;i <= n;++ i)
f[i] = read(),r = max(r,f[i]);
for(register int i = 1;i <= m;++ i)
{
int x = read(),y = read(),z = read();
add(x,y,z);
add(y,x,z);
}
int qwq = r;
r ++;
int l = 0;
while(l < r)
{
int mid = (r + l) >> 1;
if(check(mid))r = mid;
else l = mid + 1;
}
if(l == qwq + 1)
{
cout << "AFK" << endl;
return 0;
}
cout << l << endl;
return 0;
}为什么最后两个点WA?
回复可回关
by szrgjxms @ 2024-08-23 21:39:29
if (!check(inf)){
cout << "AFK";
return 0;
}在输入完后特判一下，如果所有都开通任然不满足条件，剩下的肯定也不会满足
by szrgjxms @ 2024-08-23 21:41:24
@SBBSBSBSBSB
by SBBSBSBSBSB @ 2024-08-23 21:49:27
@szrgjxms 谢谢
by SBBSBSBSBSB @ 2024-08-23 22:01:30
@szrgjxms
可以再详细一点吗
记录
只因我太菜
by szrgjxms @ 2024-08-23 22:10:48
特判是因为 如果交无穷大的费用都过不去的话，说明不能从点1走到点n
by szrgjxms @ 2024-08-23 22:12:44
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
const int M=100010;
const long long inf=0x3fffffff;
int n,m,b,u,v;
int l,r,mid;
long long int wi;
struct node{
int a;
long long int dis;
friend bool operator<(node x,node y)
{
return x.dis>y.dis;
}
};
priority_queue<node> q;
int top,g[N],f[N];
long long int dis[N];
bool vis[N];
struct edge{
int adj,nex;
long long int w;
}e[M];
void add(int x,int y,long long int wor)
{
e[++top]={y,g[x],wor};
g[x]=top;
}
void Dijkstra(int maxn)
{
for(int i=1;i<=n;i++)
{
dis[i]=inf;
vis[i]=0;
}
dis[1]=0;
while(!q.empty())
q.pop();
q.push({1,dis[1]});
while(!q.empty())
{
node now=q.top();
q.pop();
int x=now.a;
if(vis[x])
continue;
vis[x]=1;
for(int i=g[x];i;i=e[i].nex)
{
int p=e[i].adj;
if(f[p]>maxn)
continue;
if(dis[x]+e[i].w<dis[p])
{
dis[p]=dis[x]+e[i].w;
q.push({p,dis[p]});
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&b);
for(int i=1;i<=n;i++)
{
scanf("%d",f+i);
r=max(r,f[i]);
}
l=max(f[1],f[n]);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&wi);
if(u!=v)
{
add(u,v,wi);
add(v,u,wi);
}
}
while(l<r)
{
mid=(l+r)>>1;
Dijkstra(mid);
if(dis[n]>b)
l=mid+1;
else
r=mid;
}
Dijkstra(l);//最后再跑一边看看能否到达
if(dis[n]>b)
printf("AFK");
else
printf("%d",l);
return 0;
} by szrgjxms @ 2024-08-23 22:14:38
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
const int inf = 0x7f7f7f7f;
int n, m, b, cnt, maxk;
int head[maxn], dis[maxn], a[maxn];
bool vis[maxn];
struct edge {
int to, next;
long long val;
} e[maxn];
void add(int u, int v, int w){
e[++cnt].next = head[u], e[cnt].to = v, e[cnt].val = w, head[u] = cnt;
}
struct node{
int dis, pos;
bool operator < (const node &x) const{
return x.dis < dis;
}
};
priority_queue<node> q;
bool Dijkstra(int x){
if (a[1] > x) return false;
for (int i = 1; i <= n; i++)
dis[i] = inf;
dis[1] = 0;
q.push((node){0, 1});
while (!q.empty()){
node tmp = q.top();
q.pop();
int u = tmp.pos, d = tmp.dis;
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = e[i].next){
int v = e[i].to;
if (dis[v] > dis[u] + e[i].val && a[v] <= x){
dis[v] = dis[u] + e[i].val;
// if(!vis[v]) {
q.push((node){dis[v], v});
// }
}
}
}
if (dis[n] > b)
return false;
return true;
}
int main(){
cin >> n >> m >> b;
for (int i = 1; i <= n; i++) {
cin >> a[i];
maxk = max(maxk, a[i]);
}
for (int i = 1, u, v, w; i <= m; i++){
cin >> u >> v >> w;
add (u, v, w); add (v, u, w);
}
if (!Dijkstra(inf)){//就是在这里特判
cout << "AFK";
return 0;
}
int l = max(a[1], a[n]), r = maxk, mid = (l + r) >> 1;
while (l < r){
memset (vis, 0, sizeof vis);
memset (dis, 0, sizeof dis);
if (Dijkstra(mid)){
r = mid;
} else {
l = mid + 1;
}
mid = (l + r) >> 1;
}
cout << l << endl;
return 0;
}
这个应该和你的比较像，你可以看这个by szrgjxms @ 2024-08-23 22:19:07
@SBBSBSBSBSB 你的那个 MAX 改为 0x3f3f3f3f 应该就行了
by SBBSBSBSBSB @ 2024-08-24 08:13:02
@szrgjxms 谢谢 记录