二分最大钱数即可。
1 #include <cstdio> 2 #include <queue> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 typedef long long ll; 7 struct pot 8 { 9 int x; 10 ll dis; 11 pot (int _x = 0,ll _dis = 0) : x(_x),dis(_dis) {} 12 friend bool operator < (pot a,pot b) 13 { 14 return a.dis > b.dis; 15 } 16 }; 17 int head[11000],to[110000],cst[110000],nxt[110000],val[110000]; 18 bool vis[11000]; 19 ll dis[11000]; 20 priority_queue <pot> que; 21 int b,n,m,cnt; 22 void add(int x,int y,int v) 23 { 24 nxt[++cnt] = head[x]; 25 to[cnt] = y; 26 head[x] = cnt; 27 val[cnt] = v; 28 } 29 void dijkstra(int s,int lmt) 30 { 31 for(int i=1; i<= n; i++) dis[i]=2e14; 32 que.push(pot(s,0)); 33 dis[s]=0; 34 memset(vis,0,sizeof(vis)); 35 while(!que.empty()) 36 { 37 pot now=que.top(); 38 que.pop(); 39 if(vis[now.x]) continue; 40 vis[now.x]=true; 41 for(int i = head[now.x]; i; i=nxt[i]) 42 { 43 if (cst[to[i]] > lmt) continue; 44 if(dis[to[i]]>dis[now.x]+val[i]) 45 { 46 dis[to[i]]=dis[now.x]+val[i]; 47 que.push(pot(to[i],dis[to[i]])); 48 } 49 } 50 } 51 } 52 int main() 53 { 54 scanf("%d%d%d",&n,&m,&b); 55 for (int i = 1;i <= n;i++) scanf("%d",&cst[i]); 56 int tx,ty,tv; 57 for (int i = 1;i <= m;i++) 58 { 59 scanf("%d%d%d",&tx,&ty,&tv); 60 add(tx,ty,tv); 61 add(ty,tx,tv); 62 } 63 int l = 0,r = 1000000000,mid; 64 while (l < r) 65 { 66 mid = l + r >> 1; 67 dijkstra(1,mid); 68 if (dis[n] <= b) r = mid; 69 else l = mid + 1; 70 } 71 dijkstra(1,l); 72 if (dis[n] <= b) printf("%d ",l); 73 else printf("AFK "); 74 return 0; 75 }