Submission #2970516

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'

using namespace std;

typedef long long ll;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = INT_MAX;
const ll MOD = 1e9+7;

typedef ll Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void Dijkstra(const Graph &g, int s,
              vector<Weight> &dist, vector<int> &prev) {
    int n = (int)g.size();
    dist.assign(n, INF); dist[s] = 0;
    prev.assign(n, -1);
    priority_queue<Edge> Q; // "e < f" <=> "e.weight > f.weight"
    for (Q.push(Edge(-2, s, 0)); !Q.empty(); ) {
        Edge e = Q.top(); Q.pop();
        if (prev[e.dst] != -1) continue;
        prev[e.dst] = e.src;
        for(Edge f: g[e.dst]) {
            if (dist[f.dst] > e.weight+f.weight) {
                dist[f.dst] = e.weight+f.weight;
                Q.push(Edge(f.src, f.dst, e.weight+f.weight));
            }
        }
    }
}
int main() {
  int K;cin >> K;
  Graph g(K);
  repeat(i,K-1){
    g[i+1].push_back({(int)i+1,(int)(i+2)%K,1});
    g[i+1].push_back({(int)i+1,(int)(i+1)*10%K,0});
  }
  vector<Weight> dist;
  vint prev;
  Dijkstra(g,1,dist,prev);
  cout << dist[0]+1 << endl;
  return 0;
}

Submission Info

Judge Result