You Are Given a Decimal String...(CodeForces - 1202B)

제목.
Suppose you have a special x-y-counter. This counter can store some value as a decimal number; at first, the counter has value 0.
The counter performs the following algorithm: it prints its lowest digit and, after that, adds either x or y to its value. So all sequences this counter generates are starting from 0. For example, a 4-2-counter can act as follows:

it prints 0, and adds 4 to its value, so the current value is 4, and the output is 0;

it prints 4, and adds 4 to its value, so the current value is 8, and the output is 04;

it prints 8, and adds 4 to its value, so the current value is 12, and the output is 048;

it prints 2, and adds 2 to its value, so the current value is 14, and the output is 0482;

it prints 4, and adds 4 to its value, so the current value is 18, and the output is 04824.

This is only one of the possible outputs; for example, the same counter could generate 0246802468024 as the output, if we chose to add 2 during each step.
You wrote down a printed sequence from one of such x-y-counters. But the sequence was corrupted and several elements from the sequence could be erased.
Now you’d like to recover data you’ve lost, but you don’t even know the type of the counter you used. You have a decimal string s — the remaining data of the sequence.
For all 0≤x,y<10, calculate the minimum number of digits you have to insert in the string s to make it a possible output of the x-y-counter. Note that you can’t change the order of digits in string s or erase any of them; only insertions areallowed.
Input The first line contains a single string s (1≤|s|≤2⋅10^6, si∈{0−9}) — the remaining data you have. It’s guaranteed that s1=0.
Output Print a 10×10 matrix, where the j-th integer (0-indexed) on the i-th line (0-indexed too) is equal to the minimum number of digits you have to insert in the string s to make it a possible output of the i-j-counter, or −1 if there is no way to do so.
╮╯
특수한 x-y 계수기를 가지고 있다고 가정해 보세요.이 계수기는 몇몇 십진수 값을 저장할 수 있다.우선 계수기의 값은 0이다.
계수기는 아래 알고리즘을 실행합니다. 가장 낮은 위치를 인쇄한 다음 값에 x나 y를 추가합니다.따라서 이 카운터가 생성하는 모든 서열은 0에서 시작합니다.예를 들어 4-2 카운터는 다음과 같이 할 수 있습니다.
1. 0을 인쇄하고 그 값을 4로 더하기 때문에 현재 값은 4이고 출력은 0이다.2. 4를 인쇄하고 그 값을 4로 더하기 때문에 현재 값은 8이고 출력은 04이다.3. 8을 인쇄하고 그 값을 4로 더하기 때문에 현재 값은 12이고 출력은 048이다.4. 2를 인쇄하고 그 값을 2로 더하기 때문에 현재 값은 14이고 출력은 0482이다.5. 4를 인쇄하고 4를 더하기 때문에 현재 값은 18이고 출력은 04824입니다.
이것은 가능한 산출 중의 하나일 뿐이다.예를 들어 만약에 우리가 각 단계에 2를 추가하기로 선택하면 같은 계수기는 0246802468024를 출력으로 생성할 수 있다.
그 중 x-y 계수기에서 인쇄 시퀀스를 기록했습니다.그러나 서열이 파괴되어 서열 중의 몇 개의 요소가 삭제될 수 있다.
현재 잃어버린 데이터를 복구하고 싶지만, 사용한 계수기의 종류조차 모릅니다.10진 문자열 s - 서열의 나머지 데이터를 가지고 있습니다.
모든 0≤x, y<10에 대해 x-y계수기의 가능한 출력이 되도록 문자열s에 삽입해야 하는 최소 위치를 계산합니다.문자열 s의 숫자 순서를 변경하거나 삭제할 수 없습니다.삽입만 허용됩니다.
첫 번째 행에는 단일 문자열 s(1≤|s |≤ 2⋅ 10^ 6,si∈{0-9}) - 나머지 데이터가 포함되어 있습니다.보증 s1 = 0.
출력 인쇄 10×10 행렬, 그 중에서 i행 (0행 인덱스) 의 j 정수 (0 인덱스) 는 문자열 s에 삽입해야 하는 최소 비트와 같아서, ij계수기의 가능한 출력이 되도록 하고, 방법이 없으면 -1을 출력합니다.
사고방식: 이 문제의 사고방식은 매우 간단하지만 해법이 비교적 교묘하다. 우선, 우리는 각 x-y계수기에 대해 0-9 두 숫자 사이에 최소한 몇 개의 x나 y를 넣어야 전환할 수 있는지 통계해야 한다. 왜냐하면 10이기 때문이다.×10, 그래서 통계는 시간이 많이 걸리지 않고 문자열의 길이를 더하기 때문에 반드시 수조로 기록해야 한다. 관건은 두 숫자가 변환될 수 있는지 판단하는 것이다. 만약에 할 수 있다면 최소한 몇 번의 변환이 필요하다. 이때 우리는 Floy의 최단로 사상을 사용할 수 있다. 매번 두 개의 변두리를 걸어서 두 점 사이의 최단로를 기록하는 것이 바로 변환의 최소 횟수를 기록하는 것이 아니다. 교묘한 사상이다. 구체적으로 아래 코드를 봐라.
코드는 다음과 같습니다. (.\\)

#include 
using namespace std;
const int inf=0x3f3f3f3f;
int dis[10][10];//       
char s[2000010];//        

int fun(int x,int y)
{
	memset(dis,inf,sizeof(dis));
	for(int i=0;i<=9;i++)//       ，     1
	dis[i][(i+x)%10]=dis[i][(i+y)%10]=1;
	 
    for(int k=0;k<=9;k++)
    for(int i=0;i<=9;i++)
    for(int j=0;j<=9;j++)
    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//        
    
    int l=strlen(s),ans=0;//        ,  cf
    for(int i=0;i<l-1;i++)
    {
    	int a=s[i]-'0';
    	int b=s[i+1]-'0';
    	if(dis[a][b]==inf)//      ，    -1 
    	return -1;
    	else
    	ans+=dis[a][b]-1;//                 ，      -1
    }
    return ans;
}

int main()
{
   scanf("%s",s);
   for(int i=0;i<=9;i++)
   {
    for(int j=0;j<=9;j++)  
    { 
      printf("%d ",fun(i,j));//       
    }
    printf("
");
   }
   return 0;
}