UVA 1599 Ideal Path

发表于 | 分类于 ，

题意：给定一个n个顶点m条边的无向图，图中可能有多重边和自环。求顶点1到顶点n最少需要经过的边数，并且输出字典序最小的边的颜色序列。

从顶点1到顶点n的最少边数可以通过BFS求得，关键是字典序最小的颜色序列。想到的做法是，从顶点n到顶点1进行BFS，得到每个顶点与顶点n的距离。之后，想象按照距离把图分层，然后从顶点1开始，每往下走一层，都选择颜色值最小的边。

若是从顶点1到顶点n进行BFS，之后再按照到顶点1的距离分层，在往下一层走时，假设某条边e(u,v)的颜色值最小，我们选择了边e，但是顶点v到顶点n可能需要（比最少边数）更多的边数！

一个坑：因为图中存在多重边，假设我们从顶点u往下一层走时，选择的最小颜色值与边e(u,v)相同，且有3000条颜色值相同的边e(u,v)，那么结点v要入队（这里使用队列维护）3000次！因此，需要保证入队一次，不然空间和时间都会爆炸😄。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>

using namespace std;

const int MAX_V = 100000 + 10;
const int INF = ~0U >> 1;

struct Edge { int to, c; };

int n, m;
vector<Edge> G[MAX_V];
int dist[MAX_V], prevv[MAX_V], color[MAX_V];
bool inque[MAX_V];

void rbfs() {
  for (int i = 1; i <= n; i++) dist[i] = INF;
  queue<int> que;
  dist[n] = 0;
  que.push(n);
  while (!que.empty()) {
    int v = que.front(); que.pop();
    if (v == 1) break;
    for (int i = 0; i < G[v].size(); i++) {
      Edge& e = G[v][i];
      int u = e.to;
      if (dist[v] + 1 < dist[u]) {
        dist[u] = dist[v] + 1;
        que.push(u);
      }
    }
  }
}

void solve() {
  queue<int> que;
  que.push(1);
  int level = dist[1];
  memset(inque, 0, sizeof(inque));
  inque[1] = true;
  while (level--) {
    int size = que.size();
    int cmin = INF;
    while (size--) {
      int v = que.front();
      que.pop(); que.push(v);
      for (int i = 0; i < G[v].size(); i++) {
        Edge& e = G[v][i];
        int u = e.to;
        if (dist[u] != dist[v] - 1) continue;
        cmin = min(cmin, e.c);
      }
    }
    size = que.size();
    while (size--) {
      int v = que.front(); que.pop();
      inque[v] = false;
      for (int i = 0; i < G[v].size(); i++) {
        Edge& e = G[v][i];
        int u = e.to;
        if (dist[u] != dist[v] - 1 || e.c != cmin || inque[u]) continue;
        que.push(u);
        prevv[u] = v;
        color[u] = e.c;
        inque[u] = true;
      }
    }
  }
}

int main() {
  while (scanf("%d %d", &n, &m) != EOF) {
    for (int i = 1; i <= n; i++) G[i].clear();
    for (int i = 0; i < m; i++) {
      int a, b, c;
      scanf("%d %d %d", &a, &b, &c);
      G[a].push_back((Edge) {b, c});
      G[b].push_back((Edge) {a, c});
    }
    rbfs();
    solve();
    printf("%d\n", dist[1]);
    vector<int> ans;
    for (int v = n; v != 1; v = prevv[v]) {
      ans.push_back(color[v]);
    }
    for (int i = ans.size() - 1; i >= 0; i--) {
      printf("%d%c", ans[i], i == 0 ? '\n' : ' ');
    }
  }
  return 0;
}