グラフにするやつ
見た目DPに見えるのでそれを考えるが、グラフに変換すると一発
modを取るのを試すとできる
- #include<iostream>
- #include<algorithm>
- #include<vector>
- #include<queue>
- #define lol(i,n) for(int i=0;i<n;i++)
- #define mod 1000000007
- typedef long long ll;
- using namespace std;
- int dis[100010],k;
- typedef pair<int,int> P;
- priority_queue<P,vector<P>,greater<P> >Q;
- int main(){
- cin>>k;
- lol(i,k)dis[i]=mod;
- Q.push(make_pair(0,0));
- int ans=mod;
- while(!Q.empty()){
- int cost=Q.top().first;
- int now=Q.top().second;
- Q.pop();
- if(!now&&cost)ans=min(ans,cost);
- if(dis[now]<=cost)continue;
- dis[now]=cost;
- Q.push(make_pair(cost,now*10%k));
- Q.push(make_pair(cost+1,(now+1)%k));
- }
- cout<<ans<<endl;
- return 0;
- }
700点チャレンジ1問目
