題目鏈接：點擊查看

題目大意：初始時給出一個數(shù)字 $y=1$ 和一個輔助數(shù)字 $x$，每回合可以執(zhí)行兩種操作中的一種：

$y=y?10$

$y=y+x?1$

問將 $y$ 變成 $n$ 的倍數(shù)最少需要操作多少次

題目分析：同余最短路，其實 $bfs$ 也是可以做的，對于 $[0,n?1]$ 的每個點分別對于兩種操作建邊：
addedge(i,(i*10)%n,1) 和 addedge(i,(i+x-1)%n,1)，然后從點 $1$ 開始跑最短路就好啦

代碼：

// Problem: Yuki with emofunc and playf // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/18196/B // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100;//頂點數(shù) const int M=2e6+100;//邊數(shù) struct Edge {int to,w,next; }edge[M];int head[N],d[N],cnt;//鏈式前向星 bool vis[N];void addedge(int u,int v,int w) {edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++; }struct Node {int to,w;Node(int TO,int W){to=TO;w=W;}bool operator<(const Node& a)const{return w>a.w;} };void Dijkstra(int st) {priority_queue<Node>q;memset(vis,false,sizeof(vis));memset(d,inf,sizeof(d));d[st]=0;q.push(Node(st,0));while(q.size()){Node cur=q.top();int u=cur.to;q.pop();if(vis[u])continue;vis[u]=true;for(int i=head[u];i!=-1;i=edge[i].next)//掃描出所有邊 {int v=edge[i].to;int w=edge[i].w;if(d[v]>d[u]+w)//更新 {d[v]=d[u]+w;q.push(Node(v,d[v]));}}} }void init() {memset(head,-1,sizeof(head));cnt=0; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int n,x;read(n),read(x);for(int i=0;i<n;i++) {addedge(i,(i*10)%n,1);addedge(i,(i+x-1)%n,1);}Dijkstra(1%n);printf("%d\n",d[0]==inf?-1:d[0]);return 0; } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的牛客 - Yuki with emofunc and playf(同余最短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。