| 34 | } |
| 35 | |
| 36 | void spfa(int st) { |
| 37 | std::queue<int> Q; |
| 38 | Q.push(st); |
| 39 | std::vector<int> inq; |
| 40 | inq.resize(n, false); |
| 41 | inq[st] = true; |
| 42 | while (!Q.empty()) { |
| 43 | int u = Q.front(); Q.pop(); |
| 44 | inq[u] = false; |
| 45 | for (int i = head[u]; i != -1; i = edges[i].n) { |
| 46 | int v = edges[i].v; |
| 47 | if (!is_key_point[v] && dis[v] > dis[u] + edges[i].l) { |
| 48 | dis[v] = dis[u] + edges[i].l; |
| 49 | if (!inq[v]) { |
| 50 | inq[v] = true; |
| 51 | Q.push(v); |
| 52 | } |
| 53 | } |
| 54 | } |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | int main(int argc, char *argv[]) |
| 59 | { |