首页 > 代码库 > PAT 天梯赛真题集（L2、L3）

PAT 天梯赛真题集（L2、L3）

2024-09-07 05:40:56   215人阅读

技术分享

题意：求点权最大的最短路，输出最短路径条数、点权值、以及最大点权的路径。

做法：Dijstra求最短路，两步：1.找最小点；2.更新路径。这题的1不变，变的是2。在更新新路径的时候，如果找到更短的路径，那么更新点权、方案数；如果路径和最短路径一样，那么比较谁的点权大，更新为点权大的结果。

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
#include <bits/stdc++.h>
#define scf0(a) scanf("%s",&a)
#define scf1(a) scanf("%d",&a)
#define scf2(a,b) scanf("%d%d",&a,&b)
#define scf3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scf4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define MEM(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define pdd pair<double,double>
#define LL long long
using namespace std;
const int maxn = 500 + 5;
const int INF = 0x3f3f3f3f;
int n, m, s, d;
int u, v, len;
int val[maxn];
int mp[maxn][maxn];
 
void Dijstra(){
    bool vis[maxn];
    MEM(vis, false);
    int dist[maxn];  //当前点的最短距离
    MEM(dist, INF);
    int tot_val[maxn];   //当前点的最大点权
    MEM(tot_val, 0);
    tot_val[s] = val[s];
    dist[s] = 0;
    vis[s] = true;
    int diff[maxn];  //当前点不同最短路径方案数
 
    for(int i = 0; i <= n; i++) diff[i] = 1;  //方案数都为1
    map<int,int>fa;  //记录路径
    fa.clear();
    fa[s] = -1;
    for(int i = 0; i < n; i++) {
        if(i != s && dist[i] < INF) {
            dist[i] = mp[s][i];
            tot_val[i] = val[s] + val[i];
            fa[i] = s;
        }
    }
 
    for(int k = 0; k < n - 1; k++){  //找 n-1 个点
 
        int minn = INF, pos;
        for(int i = 0; i < n; i++) {
            if(vis[i] == false) {
                if(dist[i] < minn) {
                    minn = dist[i];
                    pos = i;
                }
            }
        }
        vis[pos] = true;
//        cout << pos  << endl;
        for(int i = 0; i < n; i++) {
            if(vis[i] == false) {
                if(dist[pos] + mp[pos][i] < dist[i]) {
                    dist[i] = dist[pos] + mp[pos][i];
                    tot_val[i] = tot_val[pos] + val[i];
                    fa[i] = pos;
                    diff[i] = diff[pos];  //开始写成diff[i] = 1，WA了7分，应该继pos的路径数才对啊！
                }
                else if(dist[pos] + mp[pos][i] == dist[i]) {
                    diff[i] += diff[pos];      //开始写成diff[i]++， WA了7分，应该继pos的路径数才对啊！
                    if(tot_val[i] < tot_val[pos] + val[i]){
                        tot_val[i] = tot_val[pos] + val[i];
                        fa[i] = pos;
                    }
                }
            }
        }
    }
    //输出
    cout << diff[d] << ‘ ‘;
    stack<int>sta;
    int sum = val[d];
    sta.push(d);
    while(fa[d] != -1) {
        d = fa[d];
        sum += val[d];
        sta.push(d);
    }
    cout << sum << endl;
    bool cnt = false;
    while(!sta.empty()) {
        if(cnt) cout << ‘ ‘;cnt = true;
        cout << sta.top();
        sta.pop();
    }
    cout << endl;
}
int main() {
    MEM(mp, INF);
    scf4(n, m, s, d);
    for(int i = 0; i < n; i++) scf1(val[i]);
    for(int i = 0; i < m; i++) {
        scf3(u, v, len);
        mp[u][v] = min(mp[u][v], len); //数据最终不卡相同路径值，但要注意这一点
        mp[v][u] = mp[u][v];
    }
    Dijstra();
}

PAT 天梯赛真题集（L2、L3）


联系
我们