Ac码
```
#include <iostream>
#include <queue>
using namespace std;
const long long INF = 1e18;
struct Edges
{
int to , next , key;
}edge[100010];
int first[10010] , cost[10010] , cnt = 0 , n;
long long dis[10010];
bool vis[10010];
queue <int> que;
void add(int a , int b , int c)
{
edge[++cnt].to = b;
edge[cnt].key = c;
edge[cnt].next = first[a] , first[a] = cnt;
}
bool check(int lit , int hp)
{
if(lit < cost[1]) return 0;
que.push(1) , vis[1] = 1 , dis[1] = 0;
for(int i = 2; i <= n; i++) dis[i] = INF;
while(!que.empty())
{
int now = que.front();
vis[now] = 0 , que.pop();
for(int i = first[now]; i; i = edge[i].next)
{
int to = edge[i].to;
if(cost[to] > lit) continue;
if(dis[to] > (long long)(dis[now] + edge[i].key))
{
dis[to] = (long long)(dis[now] + edge[i].key);
if(!vis[to]) vis[to] = 1 , que.push(to);
}
}
}
if(dis[n] <= (long long) hp) return 1;
else return 0;
}
int main()
{
int m , b , l = 1e9 , r = 0;
cin >> n >> m >> b;
for(int i = 1; i <= n; i++)
{
cin >> cost[i];
r = max(r , cost[i]);
l = min(l , cost[i]);
}
for(int i = 1; i <= m; i++)
{
int a , b , c;
cin >> a >> b >> c;
add(a , b , c) , add(b , a , c);
}
int ans =1e9;
while(l <= r)
{
int mid = (l + r) / 2;
if(check(mid , b)) ans = mid , r = mid - 1;
else l = mid + 1;
}
if(ans < 1e9) cout << ans << endl;
else cout << "AFK" << endl;
return 0;
}
```
by SkyLiYu @ 2019-03-13 08:23:47
WA码
```
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
struct Edges
{
int next , to;
long long key;
}edge[100010];
long long first[10010] , dis[10010] , hp , cnt = 0 , date[10010] , n;
bool vis[10010];
queue <int> que;
void add(int a , int b , int c)
{
edge[++cnt].to = b , edge[cnt].key = c;
edge[cnt].next = first[a] , first[a] = cnt;
}
void spfa(int lit)
{
que.push(1);
fill(dis , dis + n + 1 , 1e18);
dis[1] = 0 , vis[1] = 1;
while(!que.empty())
{
int now = que.front();
que.pop() , vis[now] = 0;
for(int i = first[now]; i; i = edge[i].next)
{
int to = edge[i].to;
if(date[to] > lit) continue;
if(dis[now] + edge[i].key < dis[to])
{
dis[to] = dis[now] + edge[i].key;
if(!vis[to]) que.push(to) , vis[to] = 1;
}
}
}
}
bool check(int now)
{
spfa(now);
if(dis[n] <= hp) return 1;
else return 0;
}
int main()
{
//freopen("test.in" , "r" , stdin);
long long m , l , r = 0;
cin >> n >> m >> hp;
for(int i = 1; i <= n; i++)
{
cin >> date[i];
r = max(r , date[i]);
}
l = max(date[1] , date[n]);
for(int i = 1; i <= n; i++)
{
int a , b , c;
cin >> a >> b >> c;
add(a , b , c) , add(b , a , c);
}
long long ans = 1e18;
while(l <= r)
{
long long mid = (l + r) / 2;
if(check(mid)) ans = mid , r = mid - 1;
else l = mid + 1;
}
if(ans < 1e18) cout << ans << endl;
else cout << "AFK" << endl;
return 0;
}
```
by SkyLiYu @ 2019-03-13 08:24:18