洛谷陌路寻诗礼题解

题目传送门：P10178

~~受到了题面的启发，我才想起那个早已死去的算法——SPFA~~

题面总结成一句话就是：最短路只能有一条。

那么我们用最短路算法：如果有最短路，先选择最短路。如果在更新最短值时出现了冲突——即某两种方案路径长度相等时，让后来者考虑加上一个 $[1,k]$ 范围内的值，使它变长、不再是最短路（~~退出奖牌争夺~~）就好了。

对于加上的正整数值，不妨从 $1$ 开始加。 $1$ 不够就加上 $2$ ，还不够就加上 $3$ ，以此类推……在经历若干次最短路淘汰后，如果边权加上 $k$ 仍然不能满足最短路唯一的硬性需求时，代表这组数值根本就是无解的，因此需输出No。反之将试加的值记录到ans数组中去，在每组数据结束后输出即可。

同时请注意多测清空！

代码，但是 $80\;pts$

1
#include <bits/stdc++.h>
2

3
#define N 300010
4
using namespace std;
5

6
int k;
7
int h[N], to[N], ne[N], ans[N], dis[N];
8
bool st[N];
9
int idx = 0;
10

11
void add(int u, int v) {
12
    idx++;
13
    to[idx] = v;
14
    ne[idx] = h[u];
15
    h[u] = idx;
16
}
17

18
bool spfa() {
19
    queue<int> q;
20
    q.push(1);
21
    dis[1] = 0;
22
    st[1] = true;
23
    while (!q.empty()) {
24
        int top = q.front();
25
        q.pop();
26
        for (int i = h[top]; ~i; i = ne[i]) {
27
            int j = to[i];
28
            if (top == j) {
29
                ans[i] = k;
30
                continue;
31
            }
32
            int trial = 1;
33
            if (dis[j] > dis[top] + trial) {
34
                dis[j] = dis[top] + trial;
35
                if (!st[j]) q.push(j), st[j] ^= 1;
36
            } else if (dis[j] == dis[top] + trial) trial++;
37
            if (trial > k) return false;
38
            ans[i] = trial;
39
        }
40
    }
41
    return true;
42
}
43

44
int main() {
45
    ios::sync_with_stdio(false);
46
    cin.tie(nullptr);
47
    cout.tie(nullptr);
48

49
    int t, n, m;
50
    cin >> t;
51
    while (t--) {
52
        memset(dis, 0x3f, sizeof dis);
53
        memset(h, -1, sizeof h);
54
        memset(st, 0, sizeof st);
55
        idx = 0;
56

57
        cin >> n >> m >> k;
58
        for (int i = 1; i <= m; i++) {
59
            int u, v;
60
            cin >> u >> v;
61
            add(u, v);
62
        }
63
        if (spfa()) {
64
            cout << "Yes\n";
65
            for (int i = 1; i <= m; i++) cout << ans[i] << ' ';
66
        } else cout << "No";
67
        cout << endl;
68
    }
69
    return 0;
70
}

这段代码居然一反常态的在第一组测试点处TLE了？？？于是重新看到数据范围—— $n,m\leq 5$ ，发现竟然是清空的memset出了问题！当你定义了一个大小为 $3\times10^5$ 的数组时，调用memset的结果就是对这整个 $3\times10^5$ 的空间进行内存赋值，而且估计第一组测试点出了一个比较大的询问个数 $t$ ，导致TLE。

解决方案就是从 $1$ 循环到 $n$ 清空，避免不必要的性能浪费

代码 $100\;pts$

1
#include <bits/stdc++.h>
2

3
#define N 300010
4
using namespace std;
5

6
int k;
7
int h[N], to[N], ne[N], ans[N], dis[N];
8
bool st[N];
9
int idx = 0;
10

11
void add(int u, int v) {
12
    idx++;
13
    to[idx] = v;
14
    ne[idx] = h[u];
15
    h[u] = idx;
16
}
17

18
bool spfa() {
19
    queue<int> q;
20
    q.push(1);
21
    dis[1] = 0;
22
    st[1] = true;
23
    while (!q.empty()) {
24
        int top = q.front();
25
        q.pop();
26
        for (int i = h[top]; ~i; i = ne[i]) {
27
            int j = to[i];
28
            if (top == j) {
29
                ans[i] = k;
30
                continue;
31
            }
32
            int trial = 1;
33
            if (dis[j] > dis[top] + trial) {
34
                dis[j] = dis[top] + trial;
35
                if (!st[j]) q.push(j), st[j] ^= 1;
36
            } else if (dis[j] == dis[top] + trial) trial++;
37
            if (trial > k) return false;
38
            ans[i] = trial;
39
        }
40
    }
41
    return true;
42
}
43

44
int main() {
45
    ios::sync_with_stdio(false);
46
    cin.tie(nullptr);
47
    cout.tie(nullptr);
48

49
    int t, n, m;
50
    cin >> t;
51
    while (t--) {
52
        cin >> n >> m >> k;
53
        for (int i = 1; i <= n; i++) {
54
            idx = 0;
55
            dis[i] = 0x3f3f3f3f;
56
            st[i] = false;
57
            h[i] = -1;
58
            ans[i] = 0;
59
        }
60
        for (int i = 1; i <= m; i++) {
61
            int u, v;
62
            cin >> u >> v;
63
            add(u, v);
64
        }
65
        if (spfa()) {
66
            cout << "Yes\n";
67
            for (int i = 1; i <= m; i++) cout << ans[i] << ' ';
68
        } else cout << "No";
69
        cout << endl;
70
    }
71
    return 0;
72
}

~~发现第一组数据跑得飞快，完全不见了方才TLE时的拖沓！~~

本蒟蒻第一篇题解，害怕~

音乐

JustPureH₂O

穷方圆平直之情，尽规矩准绳之用

音乐

支持与分享

评论区

音乐

目录

音乐

JustPureH2O

穷方圆平直之情，尽规矩准绳之用

音乐

洛谷 陌路寻诗礼 题解

支持与分享

评论区

音乐

目录

JustPureH₂O

洛谷陌路寻诗礼题解