0%

BZOJ 2763 解题报告

发表于 更新于 分类于 ， ，

题意简述

给定一个\(n(2 \leq n \leq 10 ^ 4)\)个点，\(m(1 \leq \ 5 * 10 ^ 4)\)条边的有权无向图，\((0 \leq 边权 \leq n)\)，你可以将其中的\(k(0 \leq k \leq 10)\)条边的边权设为\(0\)，给定起点和终点，求起点到终点的最短路径。

时间限制（总）：10s 空间限制：128MB

题目链接

BZOJ 2763

题解

题目要求最短路，所以使用最短路算法解决。但与普通的最短路不同，可以选择图中\(k\)条边使其变为\(0\)权边，所以可以把图复制\(k\)次，第\(i\)层图代表将\(i\)条边权设为\(0\)后的最短路，然后每次在最短路松弛过程中同时对上一层的点进行松弛。因为\(k\)层图自身是相同的，所以可以一次性对\(k\)层图进行松弛，而不需要真正复制k次图，只是利用这种思想来理解。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 10010;
const int MAXM = 100010;
const int MAXK = 11;
const int INF = 0x3f3f3f3f;

template<typename T>
T read() {
    T result = 0;int f = 1;char c = getchar();
    while(c > '9' || c < '0') {if(c == '-') f *= -1;c = getchar();}
    while(c <= '9' && c >= '0') {result = result * 10 + c - '0';c = getchar();}
    return result * f;
}

struct Graph {
    struct Edge {
        int next,to,weight;
    };
    Edge edges[MAXM];
    int tot,heads[MAXN];

    Graph() : tot(0) {
        memset(heads,-1,sizeof(heads));
    }

    void addEdge(int u,int v,int w) {
        edges[tot].next = heads[u];
        edges[tot].to = v;
        edges[tot].weight = w;
        heads[u] = tot++;
    }

    void addTwoEdges(int u,int v,int w) {
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
} graph;

int n,m,k,dis[MAXN][MAXK];
bool visit[MAXN];

void spfa(int S) {
    memset(dis,INF,sizeof(dis));
    memset(visit,false,sizeof(visit));
    queue<int> que;
    que.push(S);
    for(int i = 0;i <= k;i++) {
        dis[S][i] = 0;
    }
    visit[S] = true;
    while(!que.empty()) {
        int now = que.front();
        que.pop();
        visit[now] = false;
        for(int nowK = 0;nowK <= k;nowK++) {
            for(int i = graph.heads[now];i != -1;i = graph.edges[i].next) {
                Graph::Edge &tmpEdge = graph.edges[i];
                if(dis[now][nowK] + tmpEdge.weight >= dis[tmpEdge.to][nowK]) continue;
                dis[tmpEdge.to][nowK] = dis[now][nowK] + tmpEdge.weight;
                if(!visit[tmpEdge.to]) {
                    visit[tmpEdge.to] = true;
                    que.push(tmpEdge.to);
                }
            }
            if(nowK == k) continue;
            for(int i = graph.heads[now];i != -1;i = graph.edges[i].next) {
                Graph::Edge &tmpEdge = graph.edges[i];
                if(dis[now][nowK] >= dis[tmpEdge.to][nowK + 1]) continue;
                dis[tmpEdge.to][nowK + 1] = dis[now][nowK];
                if(!visit[tmpEdge.to]) {
                    visit[tmpEdge.to] = true;
                    que.push(tmpEdge.to);
                }
            }

        }
    }
}

int main() {
    n = read<int>(); m = read<int>(); k = read<int>();
    int s = read<int>(),t = read<int>();
    for(int i = 0;i < m;i++) {
        int a = read<int>(),b = read<int>(),c = read<int>();
        graph.addTwoEdges(a,b,c);
    }
    spfa(s);
    printf("%d\n",dis[t][k]);
    return 0;
}