P1462 二分

#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define SI(a) scanf("%d",&a) #define ms(a,x) memset(a,x,sizeof(a)) typedef long long ll; const int mod = 998244353; const int maxn = 1e6+10; using namespace std; int ans; int a[maxn]; struct Edge{ int from,to,dis; }; struct HeapNode{ int d,u; bool operator < (const HeapNode& rhs) const{ return d > rhs.d; } }; int n,m,b;//点数，边数,起始 int cnt; vector<Edge>edges; vector<int>G[maxn];//每个节点出发的边编号 bool done[maxn]; int dis[maxn];//距离 int p[maxn];//最短路的上一条边 void init(int n){ for(int i = 0;i <= n;i++)G[i].clear(); cnt = 0; edges.clear(); } void AddEdge(int from,int to,int dis){ edges.push_back((Edge){from,to,dis}); //edges.push_back((Edge){to,from,dis});//无向图/边 cnt = edges.size(); G[from].push_back(cnt-1); } bool Dijkstra(int val){ priority_queue<HeapNode>Q; for(int i = 0;i <= n;i++)dis[i] = INF; dis[1] = 0; //for(int i = 0;i < n;i++)cout<<dis[i]<<endl; ms(done,false); Q.push((HeapNode){0,1}); while(!Q.empty()) { HeapNode x = Q.top();Q.pop(); int u = x.u; if(done[u])continue; done[u] = true; //cout<<"1 "<<G[u].size()<<endl; for(int i = 0;i <(int)G[u].size();i++) { Edge& e = edges[G[u][i]]; //cout<<e.dis<<endl; if(dis[e.to] > dis[u] + e.dis && a[e.to] <= val){ dis[e.to] = dis[u]+ e.dis; //p[e.to] = G[u][i]; Q.push((HeapNode){dis[e.to],e.to}); } } } /*for(int i = 1;i <= n;i++) cout<<dis[i]<<endl;*/ return dis[n] <= b; } int main() { int l,r = -1; cin>>n>>m>>b; //cout<<n<<" "<<m<<" "<<b<<endl; init(n); for(int i = 1;i <= n;i++){ scanf("%d",&a[i]); if(r < a[i]) r = a[i]; } /*for(int i = 1;i <= n;i++) cout<<a[i]<<endl;*/ l = min(a[1],a[n]); //cout<<l<<" "<<r<<endl; //cout<<"haha"<<endl; for(int i = 0;i < m;i++) { int u,v,dis; cin>>u>>v>>dis; AddEdge(u,v,dis); AddEdge(v,u,dis); } if(!Dijkstra(r))cout<<"AFK"<<endl; else{ while(l != r) { int mid = l + (r-l)/2; //cout<<mid<<endl; if(!Dijkstra(mid))l = mid+1; else r = mid ; } cout<<l<<endl; } return 0; }