参考题解
题意：求0->1路径上的数组成真小数最小值
若最小路径无环，则长度 \(\le\) n-1
方法一
从 \(0\) 开始，维护当前走到的点，每次都走边权（当前总体）最小的且 \(v\) 能到 \(1\) 的边，跑 \(2n\) 条边，
顺便沿路维护走过的边权
连 \(1\rarr 1\)代价为 \(0\) 的环，这样最后一定是在环里。在边权数组的 \(n+1\) 到 \(2n\) 项中一定存在循环，直接找最小周期即可（\(|s|-border(s)\)）
方法二（要连 \(0\rarr 0\) 代价为 \(0\) 的环）
从小到大考虑到 1 点路径的距离，同时维护 路径距离为 i 时从 u 出发的路径最小排名为多少：\(f[u][i]\)
从 \(i \rarr i+1\) 时，以边权为第一关键字，\(f[v][i]\) 为第二关键字排序，得到 \(f[u][i+1]\)
同时维护路径（使 \(f[u][i+1]\) 最优的决策点 \(v\)）
路径长度跑到 \(2n\) ，把最优路径抠出来，找环算贡献
第一种跟模拟赛上想到的思路比较接近（贪心），下面是代码。
#include<bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int maxn = 4e3 + 10,mod = 1e9 + 7;
inline int rd(){
int res = 0,f = 0;
char ch = getchar();
for(;!isdigit(ch);ch = getchar()) if(ch == '-') f = 1;
for(;isdigit(ch);ch = getchar()) res = res * 10 + ch - 48;
return f ? -res : res;
}
int t,head[maxn],tot,n,m,ok[maxn],ans[maxn],s[maxn],nxt[maxn],len;
struct edge{int to,nex,w;}e[maxn];
ll inv,fans;
inline ll qp(ll x,int k,ll ans = 1){
for(;k;k>>=1,x=x*x%mod) if(k&1) ans=ans*x%mod;
return ans;
}
inline void add(int u,int v,int w){e[++tot] = (edge){v,head[u],w}; head[u] = tot;}
vector<int> to[maxn],now,nex;
void dfs(int u){ok[u] = 1; for(auto v : to[u]) if(!ok[v]) dfs(v);}
int main(){
t = rd(),inv = qp(10,mod - 2);
int mnw;
for(ri cas = 1;cas <= t;++cas){
n = rd(),m = rd();
tot = 0;
for(ri i = 0;i < n;++i) ok[i] = head[i] = 0,to[i].resize(0);
for(ri i = 1,u,v,w;i <= m;++i) u = rd(),v = rd(),w = rd(),add(u,v,w),to[v].push_back(u);
add(1,1,0);
dfs(1);
now.resize(0),nex.resize(0);
now.push_back(0);
for(ri k = 1;k <= 2 * n;++k){
mnw = 10;
for(auto u : now)
for(ri i = head[u];i;i = e[i].nex) if(ok[e[i].to]) mnw = min(e[i].w,mnw);
ans[k] = mnw,nex.resize(0);
for(auto u : now)
for(ri i = head[u];i;i = e[i].nex) if(ok[e[i].to] && e[i].w == mnw) nex.push_back(e[i].to);
sort(nex.begin(),nex.end());
nex.resize(unique(nex.begin(),nex.end())-nex.begin());
swap(now,nex);
}
for(ri i = n+1;i <= 2*n;++i) s[i-n] = ans[i];
nxt[1] = 0;
for(ri i = 2,j = 0;i <= n;++i){
while(j && s[j+1] != s[i]) j = nxt[j];
if(s[j+1] == s[i]) ++j;
nxt[i] = j;
}
len = n - nxt[n]; fans = 0;
for(ri i = 1;i <= len;++i) fans = (fans * 10 + s[i]) % mod;
fans = fans * qp(qp(10,len)-1,mod - 2) % mod; fans = fans * 10 % mod;
for(ri i = n;i >= 1;--i) fans = (fans * inv + ans[i]) % mod;
fans = fans * inv % mod;
printf("Case #%d: %lld\n",cas,fans);
}
return 0;
}