通往奥格瑞玛的道路

二分+Dijkstra

#include<bits/stdc++.h>
using namespace std;
const int MAXV = 10005;
const int INF = 1000000005;                      //∞

struct edge{                                    //城市分布
  int v;                                        //城市临近公路
  int w;                                        //损失血量
  edge(int _v, int _w): v(_v), w(_w) {}         //构造函数: v(_v) 和 v = _v 意思相同写法不同，第二种要放到大括号里
  edge(){}                                      //重载函数：可以不初始化的新建变量
};
struct node{ //结构体内嵌比较函数
  int v; //城市临近公路
  int d; //过路费
  friend bool operator < (const node &a, const node &b)   //友元：重载小于号“<”
  {
    return a.d > b.d;                           //d大的优先级高
  }
  node(int _v, int _d): v(_v), d(_d) {}
  node(){}
};

int d[MAXV];                                   //记录最短路径
vector<edge> G[MAXV];                          //图的邻接表表示
priority_queue<node> pq;                       //使用node结构体创建优先级队列
int cost[MAXV];                                //需要交费
int vis[MAXV];                                 //记住过往
int n, m, b;                                   //点、边、血量

bool dijkstra(int s)
{
  if(cost[1] > s)                             //寻找最大值时比较起点位置
  return false;
  fill(d, d+MAXV, INF);                       //空数组的初始化
  fill(vis, vis+MAXV, false);
  d[1] = 0;                                  //起点
  pq.push(node(1,0));                        //队列末尾添加起点
  while(!pq.empty())                         //非空
  {
    int u = pq.top().v;                      //返回首元素里的v
    pq.pop();                                //删除队列首元素
    if(vis[u])                               //减少重复计算
      continue;
    vis[u] = true;                           //动态规划：标记已计算
    for(int i = 0; i < G[u].size(); i++)     //遍历u城的连接线
    {
      int v = G[u][i].v;                     //权：u城市到v城市
      int l = G[u][i].w;                     //进城费用
      if(d[u]+l < d[v] && cost[v] <= s)      //贪心算法：限制进城费用，逼近最值
      {
        d[v] = d[u]+l;                       //更新最短路
        pq.push(node(v, d[v]));              //队列末尾添加最短路
      }
    }
  }
  if(d[n] <= b)                              //剩余血量大于等于0
    return true;
  else                                       //剩余血量低于0
    return false;
}
int main()
{
  scanf("%d%d%d",&n,&m,&b);
  int most = 0, least = INF;
  for(int i = 1; i <= n; i++)
  {
    scanf("%d",&cost[i]);
    most = max(most, cost[i]);               //找出二分的最大最小边界
    least = min(least, cost[i]);
  }
  //也可以用一个数组存每个值，然后sort排序之后，只要对数组内的数二分，时间复杂度会更低一些
  for(int i = 1; i <= m; i++)
  {
    int ai, bi, ci;
    scanf("%d%d%d",&ai,&bi,&ci);
    G[ai].push_back(edge(bi, ci));           //建立无向图的连接
    G[bi].push_back(edge(ai, ci));
  }
  if(!dijkstra(INF))                         //判断能否通过
  //特判是否联通,不能用least>mid因为可能是相等退出，但未夹出的相等位置
  //也可以做标记flag，看是否至少成立一次
  {
    printf("AFK");
    return 0;
  }
  while(most > least)                        //寻找最值
  {
    int mid = most + (0.5*(least-most));     //二分法
    if(dijkstra(mid))                        //最短路径里寻找最值
      most = mid;                            //压缩二分右端
    else
      least = mid+1;                         //压缩二分左端
  }
  printf("%d",least);
  return 0;
}

笔记：这个语文不好真的题目也读不懂，“交费最多的最小值”是指最短路线里的交费最多的城市。先用dojkstra计算最短距离能不能通过，再用二分法输出最值