KK_lang @ 2023-02-18 09:15:38
估计是 Hack 数据，找了快
#include<bits/stdc++.h>
using namespace std;
int n, m, b, f[10010];
long long d[10010];
bool vis[10010];
struct Edge
{
int v, w;
Edge(int v, int w) : v(v), w(w) {}
};
struct Node
{
int u;
long long d;
Node(int u, long long d) : u(u), d(d) {}
bool operator < (const Node &a) const
{ return d > a.d; }
};
vector<Edge> adj[10010];
void dijkstra(int mid)
{
memset(d, 0x3f, sizeof(d));
memset(vis, false, sizeof(vis));
d[1] = 0;
priority_queue<Node> q;
q.push((Node){1, 0});
while (!q.empty())
{
int u = q.top().u;
q.pop();
if (u == n) return;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < adj[u].size(); i++)
{
int v = adj[u][i].v, w = adj[u][i].w;
if (f[v] > mid) continue;
if (d[v] > d[u] + w)
{
d[v] = d[u] + w;
q.push((Node){v, d[v]});
}
}
}
}
void dijkstra_lt()
{
memset(d, 0x3f, sizeof(d));
memset(vis, false, sizeof(vis));
d[1] = 0;
priority_queue<Node> q;
q.push((Node){1, 0});
while (!q.empty())
{
int u = q.top().u;
q.pop();
if (u == n) return;
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < adj[u].size(); i++)
{
int v = adj[u][i].v, w = adj[u][i].w;
if (d[v] > d[u] + w)
{
d[v] = d[u] + w;
q.push((Node){v, d[v]});
}
}
}
}
int main()
{
cin >> n >> m >> b;
for (int i = 1; i <= n; i++) cin >> f[i];
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back((Edge){v, w});
adj[v].push_back((Edge){u, w});
}
dijkstra_lt();
if (d[n] > b) cout << "AFK" << endl;
else
{
int l = min(f[1], f[n]), r = 0, ans;
for (int i = 1; i <= n; i++) r = max(r, f[i]);
while (l <= r)
{
int mid = (l + r) / 2;
dijkstra(mid);
if (d[n] <= b) ans = mid, r = mid - 1;
else l = mid + 1;
}
cout << ans << endl;
}
return 0;
}by codejiahui @ 2023-02-18 11:56:31
@KK_lang 你还在调这个吗……
by codejiahui @ 2023-02-18 11:59:12
@KK_lang
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
int n,m,b,f[10010];
int d[10010],vis[10010];
struct Edge{int v,w;};
struct Node
{
int u,d;
bool operator<(const Node &a) const
{
return d > a.d;
}
};
vector<Edge> adj[10010];
priority_queue<Node> q;
bool dijkstra(int mid)
{
while(!q.empty())
q.pop();
memset(vis,0,sizeof(vis));
memset(d,0x3f,sizeof(d));
d[1] = 0;
if (f[1] > mid) return false;
q.push({1,0});
while(!q.empty())
{
int u = q.top().u;
q.pop();
if (u == n) return true;
if (vis[u]) continue;
vis[u] = 1;
for (auto x:adj[u])
if (f[x.v] <= mid && d[x.v] > d[u] + x.w)
{
if (d[u] + x.w > b) continue;
d[x.v] = d[u] + x.w;
q.push({x.v,d[x.v]});
}
}
return false;
}
int main()
{
scanf("%d%d%d",&n,&m,&b);
int maxn = 0;
for (int i = 1;i <= n;i++)
{
scanf("%d",&f[i]);
maxn = max(maxn,f[i]);
}
for (int i = 1;i <= m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
int l = f[1],r = maxn,ans = -1;
while(l <= r)
{
int mid = (l + r) / 2;
if (dijkstra(mid))
{
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
if (ans == -1) printf("AFK\n");
else printf("%d\n",ans);
return 0;
}