Luobuyu's Blog

0%

3856.最短路径

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 1.9k 阅读时长 ≈ 2 分钟
注意边的长度特点，考虑最小生成树，然后dfs

nowcoder-3856.最短路径

题目描述：

$ N $ 个城市，标号从 $ 0 $ 到 $ N-1 $ ， $ M $ 条道路，第 $ K $ 条道路（ $ K $ 从 $ 0 $ 开始）的长度为 $ 2^K $ ，求编号为 $ 0 $ 的城市到其他城市的最短距离

数据范围：
$ 2\le N \le 100, M \le 500 $

题解：

注意存在重边。

因为是 $ 2^k $ ，所以当前的边 $ i $ 一定比它前面所以的边加起来还要长。因此如果之前联通，那么边就不需要加了。变成了kruskal 问题，然后 dfs 一遍找出根 0 到其他点的距离。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
using namespace std;
using namespace FAST_IO;
const ll mod = 1e5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e2 + 10;
int t, n, m, k;
int g[maxn][maxn];
bool flag[maxn][maxn];
int fa[maxn];

int getFa(int u)
{
    return fa[u] == u ? u : getFa(fa[u]);
}
struct Edge
{
    int u, v, w;
};
vector<Edge> edge;

ll qpow(ll a, ll b, ll mod)
{
    ll tmp = a, ans = 1;
    while (b)
    {
        if (b & 1)
        {
            ans = ans * tmp % mod;
        }
        tmp = tmp * tmp % mod;
        b >>= 1;
    }
    return ans;
}

bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}
int dis[maxn];
bool vis[maxn];
void dfs(int u)
{
    vis[u] = true;
    for (int i = 0; i < n; i++)
    {
        if (flag[u][i])
        {
            if (vis[i])
                continue;
            dis[i] = (dis[u] + qpow(2, g[u][i], mod)) % mod;
            dfs(i);
        }
    }
}

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    read(n, m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == j)
                g[i][j] = 0;
            else
                g[i][j] = INF;
            flag[i][j] = false;
        }
        fa[i] = i;
        dis[i] = INF;
        vis[i] = 0;
    }
    dis[0] = 0;
    for (int i = 0, u, v; i < m; i++)
    {
        read(u, v);
        g[u][v] = g[v][u] = min(g[u][v], i);
        edge.push_back({u, v, i});
    }
    sort(edge.begin(), edge.end(), cmp);
    int cnt = 0;
    for (int i = 0; i < m; i++)
    {
        int u = edge[i].u;
        int v = edge[i].v;
        int uf = getFa(u), vf = getFa(v);
        if (uf == vf)
            continue;
        fa[uf] = vf;
        cnt++;
        flag[u][v] = flag[v][u] = true;
        if (cnt == n - 1)
            break;
    }
    dfs(0);
    for (int i = 1; i < n; i++)
    {
        if (dis[i] == INF)
        {
            printf("-1\n");
        }
        else
        {
            printf("%d\n", dis[i]);
        }
    }

    return 0;
}