思路
一道妙妙题。
我们考虑将一条边拆成若干个点连接的链,这条链上每条边的权值都是一位数。
这样每个点一定是先尽量少经过边,这很 bfs。
对于转移,显然是选权值小的边先走。
但这可能出现一个问题,如果我要更新 \(u\),有一个 \(v_1\) 指向 \(u\) 边权为 \(x\),有一个 \(v_2\) 指向 \(u\) 边权为 \(y\),且 \(v_1\) 在队列中排在 \(v_2\) 前面,但如果 \(v_1\) 与 \(v_2\) 的答案相同, 却有 \(x > y\),这时显然不优。
因此我们将答案相同的点放在一起,每次先选最小的边进行转移,保证答案的正确性。
代码
#include<bits/stdc++.h>
#define LL long long
#define max(x...) std::max({x})
#define min(x...) std::min({x})
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
inline int rd()
{
int sign = 1, re = 0; char c = getchar();
while(!isdigit(c)){if(c == '-') sign = -1; c = getchar();}
while(isdigit(c)){re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
namespace MOD
{
const int mod = 1e9 + 7;
inline int add(int a, int b) {return a + b >= mod ? a + b - mod : a + b;}
inline int mul(int a, int b) {return 1ll * a * b % mod;}
inline int sub(int a, int b) {return a - b < 0 ? a - b + mod : a - b;}
} using namespace MOD;
int n, m, ans[1000005], tot;
std::vector<int> e[1000005][10];
std::queue<std::vector<int>> q;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
tot = n = rd(), m = rd();
FOR(i, 1, m)
{
int u = rd(), v = rd();
int bit[10], cnt = 0, h = i;
while(h) bit[++cnt] = h % 10, h /= 10;
std::reverse(bit + 1, bit + 1 + cnt);
if(cnt == 1) {e[u][bit[1]].emplace_back(v), e[v][bit[1]].emplace_back(u); continue;}
e[u][bit[1]].emplace_back(tot + 1);
FOR(j, 1, cnt - 2)
e[tot + j][bit[j + 1]].emplace_back(tot + j + 1);
e[tot + cnt - 1][bit[cnt]].emplace_back(v);
e[v][bit[1]].emplace_back(tot + cnt - 1);
FOR(j, 1, cnt - 2)
e[tot + cnt - j][bit[j + 1]].emplace_back(tot + cnt - j - 1);
e[tot + 1][bit[cnt]].emplace_back(u);
tot += cnt - 1;
}
FOR(i, 2, tot) ans[i] = -1;
q.push({1});
while(!q.empty())
{
auto now = q.front(); q.pop();
FOR(num, 0, 9)
{
std::vector<int> in;
for(int i : now) for(int j : e[i][num])
if(ans[j] == -1)
{
ans[j] = add(mul(ans[i], 10), num);
in.emplace_back(j);
}
if(!in.empty()) q.push(in);
}
}
FOR(i, 2, n) printf("%d\n", ans[i]);
return 0;
}
原文地址:http://www.cnblogs.com/zuytong/p/16807678.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性