洛谷 P1948 / loj 10074 / 一本通 1496【分层图】

坑点：求得是最大边权，dijk需要把求和改成最大值。

#include 
#define int long long

using namespace std;

vector<pair<int, int>> z[444444];
int dis[444444];
bool vis[444444];

struct Node
{
  int dis, u;
  bool operator<(const Node &a) const
  {
    return dis > a.dis;
  }
};

void dijkstra(int s)
{
  priority_queue<Node> pq;
  memset(dis, 0x3f, sizeof dis);
  dis[s] = 0;
  pq.push({0, s});
  while (pq.size())
  {
    int u = pq.top().u;
    pq.pop();
    if (!vis[u])
    {
      vis[u] = true;
      for (auto &ed : z[u])
      {
        int v = ed.first, w = ed.second;
        if (dis[v] > max(dis[u], w))
        {
          dis[v] = max(dis[u], w);
          pq.push({dis[v], v});
        }
      }
    }
  }
}

signed main()
{
  int n, m, k;
  cin >> n >> m >> k;
  int s, t;
  s = 1, t = n;
  while (m--)
  {
    int a, b, c;
    cin >> a >> b >> c;
    for (int i = 0; i <= k; i++)
      z[i * n + a].push_back({i * n + b, c}), z[i * n + b].push_back({i * n + a, c});
    for (int i = 0; i < k; i++)
      z[i * n + a].push_back({(i + 1) * n + b, 0}), z[i * n + b].push_back({(i + 1) * n + a, 0});
  }
  dijkstra(s);
  int mi = 0x3f3f3f3f3f3f3f3f;
  for (int i = 0; i <= k; i++)
    mi = min(mi, dis[i * n + t]);
  if (mi != 0x3f3f3f3f3f3f3f3f)
    cout << mi << '\n';
  else
    cout << "-1\n";
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70