传送门
这题不用想的太复杂，题意弄懂了，其实就是套一个最短路模板， 因为会存在环所以这里用SPFA跑了一遍 #include <set> #include <map> #include <cmath> #include <stack> #include <queue> #include <string> #include <vector> #include<cstring> #include <stdio.h> #include <iostream> #include <algorithm> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6+5; int t,n,m; struct Node{ int to,next,val; }edge[maxn<<4]; int head[maxn],dis[maxn],tot; bool vis[maxn]; void add_edge(int u,int v,int w){ edge[tot].to=v; edge[tot].next=head[u]; edge[tot].val=w; head[u]=tot++; } void init(){ memset(head,-1,sizeof(head)); memset(dis,INF,sizeof(dis)); memset(vis,false,sizeof(vis)); tot=0; } void buildGraph(int N, int Seed) { int nextRand = Seed; // initialize random number generator for (int x = 1; x <= N; x++) { // generate edges from Node x int w = x % 10 + 1; // the weight of edges int d = 10 - w; // the number of edges for (int i = 1; i <= d; i++) { add_edge(x, nextRand % N + 1, w); // add a new edge into G nextRand = nextRand * 233 % N; } add_edge(x, x % N + 1, w); } } void SPFA(int s){ queue<int>q; q.push(s); vis[s]=true; dis[s]=0; while (!q.empty()){ int x=q.front(); q.pop(); vis[x]=false; for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].to; if(dis[y]>dis[x]+edge[i].val){ dis[y]=dis[x]+edge[i].val; if(!vis[y]){ q.push(y); vis[y]=true; } } } } } int main() { cin>>t; int seed; while (t--){ init(); scanf("%d%d",&n,&seed); buildGraph(n,seed); SPFA(1); printf("%d\n",dis[n]); } return 0; }