CF1209F Koala and Notebook（最短路+拆点）

定义一条路径的权值为路径上所有边的编号直接相连所得到的十进制数字大小。

求1到每个点最短路mod \(10^9+7\)

做法：

每一条边可以按数位拆成若干个点。

bfs的时候，前面距离完全相同的点需要合并。

这种涉及字典序的题，都可以这样做。

细节非常多：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int mod=1e9+7;
int n,m;
vector<pair<int,int> > g[maxn];
long long d[maxn];
int vis[maxn];
//每一轮之后，距离完全相同的点，要合并成一个新点
struct qnode {
	long long w;
	vector<pair<int,int> > edges;
}; 
 
void bfs (int s) {
	queue<qnode>q;
	vector<pair<int,int> > tt=g[s];
	q.push({0,tt});
	vis[s]=1;
	d[s]=0;
	while (q.size()) {
		qnode tt=q.front();
		q.pop();
		qnode v;
		v.w=0;
		v.edges.clear();
		int pre=-1;
		for (pair<int,int> it:tt.edges) {
			if (vis[it.first]) continue;
			if (it.second!=pre) {
				v.w=(tt.w*10+pre)%mod;
				sort(v.edges.begin(),v.edges.end(),[&](pair<int,int> x,pair<int,int> y) {
					return x.second<y.second;
				});
				if (pre!=-1) q.push(v);
				v.edges.clear();
				pre=it.second;
			}
			d[it.first]=tt.w*10+it.second;//算出当前节点的最短路 
			d[it.first]%=mod;
			//printf("%d %d %d %d\n",v.w,it.first,it.second,pre);
			vis[it.first]=1;
			for (pair<int,int> it1:g[it.first]) {
				v.edges.push_back(it1);
			}
		}
		if (v.edges.size()) {
			v.w=(tt.w*10+pre)%mod;
			sort(v.edges.begin(),v.edges.end(),[&](pair<int,int> x,pair<int,int> y) {
				return x.second<y.second;
			});
			if (pre!=-1) q.push(v);
		}
	}
}


int main () {
	scanf("%d%d",&n,&m);
	int tot=n;
	for (int i=1;i<=m;i++) {
		int u,v,w;
		scanf("%d%d",&u,&v);
		w=i;
		int pre=v;
		vector<int> vv;
		vector<int> p;
		p.push_back(u);
		while (w) {
			vv.push_back(w%10);
			tot++;
			p.push_back(tot);
			w/=10;
		}   
		p.back()=v;
		for (int i=0;i<p.size()-1;i++) {
			g[p[i]].push_back({p[i+1],vv[vv.size()-1-i]});
		}
		for (int i=0;i<p.size()-1;i++) {
			g[p[i+1]].push_back({p[i],vv[i]});
		}
	}
	for (int i=1;i<=tot;i++) sort(g[i].begin(),g[i].end(),[&](pair<int,int> x,pair<int,int> y) {
		return x.second<y.second;
	});
	bfs(1);
	for (int i=2;i<=n;i++) printf("%lld\n",d[i]);
}