AtCoder Beginner Contest 077 D-Small Multiple 妙妙最短路

太妙了

将 k k k的倍数看作 k % 0 k \% 0 k%0的同余类，那么我们发现，对于任何的数字可以表达为 + 1 +1 +1和 × 10 \times 10 ×10的表达式。

我们可以发现， + 1 +1 +1会对答案产生 + 1 +1 +1的贡献，而 × 10 \times 10 ×10不会产生贡献。

那么我们从 i i i出发，向 ( i + 1 ) (i + 1) % k (i+1)建 d i s = 1 dis= 1 dis=1的边，向 i × 10 i \times 10 i×10建立 d i s = 0 dis = 0 dis=0的边(在完全剩余系中建边)，然后求 1 − 0 1-0 1−0的最短路即可。答案为最短路长度 + 1 +1 +1。

太妙了，完全想不到。。。

#include 
using namespace std;

template 
struct Graph{
    vector head, nxt; vector to; int tot, n;
    struct EdgeSet{
        int u; Graph &G;
        EdgeSet(int u, Graph &G) : u(u), G(G) {}
        struct Iter{
            int idx; Graph &G;
            Iter(int idx, Graph &G) : idx(idx), G(G) {}
            Info &operator*() { return G.to[idx]; }
            void operator++() { idx = G.nxt[idx]; }
            bool operator!=(Iter &o) { return idx != o.idx; }
        };
        Iter begin() { return Iter(G.head[u], G); }
        Iter end() { return Iter(-1, G); }
    };
    explicit Graph(int n) : head(n + 1, -1), tot(0), n(n) {}
    EdgeSet operator[](int x) { return EdgeSet(x, *this); }
    void add(int u, const Info &v){
        nxt.emplace_back(head[u]);
        to.emplace_back(v);
        head[u] = tot++;
    }
    Graph &operator= (const Graph &G){
        head = G.head, nxt = G.nxt, to = G.to;
        tot = G.tot, n = G.n;
        return *this;
    }
};

struct dijsktra{
    static constexpr long long INF = 0x3f3f3f3f3f3f3f3f;
    vector d;
    template 
    dijsktra(Graph &G, int s) : d(G.n + 1, INF){
        using Node = pair;
        priority_queue q;
        q.emplace(Node(0, s));
        d[s] = 0;
        while (!q.empty()){
            Node cur = q.top();
            q.pop();
            int u = cur.second;
            if (d[u] != -cur.first) continue;
            for (auto [v, w] : G[u]){
                if (d[u] + w > k;
    Graph g(k);
    for(int i = 1; i