最短路
Eva.Q Lv9
2022-07-03 10:21:51

“好了！”

dij

不加优化 ，复杂度为

算法思路：把所有的点分成两个集合，每次从还未打标记的集合中，选取出距离最短的点，用它来更新其他点。

第19届浙江省赛G

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
#define N 1007
 
struct node {
    double x, y;
    double sqr(double t) {return t * t;}
    double dis(node t) {return sqrt(sqr(t.x - x) + sqr(t.y - y));}
} a[N];
 
double mp[N][N], v1, v2, dis[N];
bool vis[N];
 
int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;
    cin >> a[0].x >> a[0].y >> a[n + 1].x >> a[n + 1].y >> v1 >> v2;
    for (int i = 0; i <= n + 1; ++i) {
        dis[i] = 1e18;
        for (int j = 0; j <= n + 1; ++j) {
            if (i == 0) mp[i][j] = a[i].dis(a[j]) / v1;
            else {
                double tmp = a[i].dis(a[j]);
                if (tmp > 3 * v2) mp[i][j] = 3 + (tmp - 3 * v2) / v1;
                else mp[i][j] = tmp / v2;
            }
        }
    }
    dis[0] = 0;
    for (int i = 0; i <= n + 1; ++i) {
        double mn = 1e18;
        int pos = 0;
        for (int j = 0; j <= n + 1; ++j)
            if (!vis[j] && dis[j] < mn) {mn = dis[j]; pos = j;} // 找点
        vis[pos] = 1;
        for (int j = 0; j <= n + 1; ++j)
            dis[j] = min(dis[j], dis[pos] + mp[pos][j]); // 更新
    }
    printf("%.12lf\n", dis[n + 1]);
    return 0;
}

堆优化 ，复杂度是 。所以如果边是 级别的，不如不用优化 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<pair<int, int> > e[N];
ll dis[N];
bool vis[N];
priority_queue<pair<ll, int> > Q;

void dij(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; Q.push(make_pair(0, s));
    while (!Q.empty()) {
        int u = Q.top().second; Q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [v, w] : e[u])
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push(make_pair(-dis[v], v));
            }
    }
}

Bellman-ford

复杂度是 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define N 100007

int n, dis[N];
struct edge {int u, v, w;};
vector<edge> V;

void bellman_ford(int x) {
    memset(dis, 0x3f, sizeof(dis));
    dis[x] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < V.size(); ++j) {
            dis[V[i].v] = min(dis[V[i].v], dis[V[i].u] + V[i].w);
        }
}

SPFA （队列优化的 Bellman_ford）

复杂度是 ，对于随机生成的图复杂度为线性，但是很容易构造卡到 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define N 100007

int dis[N];
vector<pair<int, int> > V[N];
bool vis[N];
queue<int> Q;

void spfa(int x) {
    memset(dis, 0x3f, sizeof(dis));
    dis[x] = 0;
    while (!Q.empty()) {
       int u = Q.front(); Q.pop(); vis[u] = 0;
       for (auto [v, w] : V[u]) {
           if (dis[v] > dis[u] + w) {
               dis[v] = dis[u] + w;
               if (!vis[v]) {Q.push(v); vis[v] = 1;}
           } 
       }
    }
}

多关键字

把 dis 改成一个结构体，比较的时候按多关键字比较规则进行比较。

分层图

有些问题的信息，可能要在跑最短路的过程中才能确定，这样的问题，我们会根据过程中，可能遇到的不同状态，来进行分层，每一层里面都是一个最基本的图，层与层之间的连边，代表着不同状态的切换。

关于要开多少点和边。点数：层数 每层的点数；边数：层数 每层的边数 (双向边) （层内 层间）

洛谷P2939

给一张图，从 号点走到 号点，可以选择 条边，将其代价变为 ，问最后的总代价最小是多少。

思路：按走了多少条代价变为 的边进行分层。

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
#define N 210007 //10000 * 21
#define M 4200007// 50000 * 21 * 2 * 2
#define ll long long

vector<pair<int, int> > e[N];
ll dis[N];
bool vis[N];
priority_queue<pair<ll, int> , vector<pair<ll, int> >, greater<pair<ll, int> > > Q;
int n;

void dij(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; Q.push(make_pair(0, s));
    while (!Q.empty()) {
        int u = Q.top().second; Q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [v, w] : e[u])
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push(make_pair(dis[v], v));
            }
    }
}

inline void add(int u, int v, int w) {
    e[u].push_back(make_pair(v, w));
}

int main() {
    n = rd(); int m = rd(), k = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(), w = rd();
        for (int j = 0; j <= k; ++j) {
            add(j * n + u, j * n + v, w);
            add(j * n + v, j * n + u, w);
            if (j == k) continue;
            add(j * n + u, (j + 1) * n + v, 0);
            add(j * n + v, (j + 1) * n + u, 0);
        }
    }
    dij(1);
    ll ans = 1e18;
    for (int i = 0; i <= k; ++i) ans = min(ans, dis[i * n + n]);
    printf("%lld\n", ans);
    return 0;
}

2022广西省赛D

有一辆小车要从起点 到终点 ，车的初始速度为 。在图上，有两类点，一类是普通的点，一类是可以花 代价进行倍速的点，提升速度为原来的两倍。边也有两类，一类是普通的边，一类是经过以后，速度会减为 。经过一条边的代价是 。问从起点到终点的最小代价（时间最短）是多少。

思路：这题我们可以根据速度分层。首先根据代价的计算方法可以知道，层数最多就是最大边权的 。然后就根据条件建图。层与层之间的边有两类，一类是加速的，加速的就从上一层连到下一层的自己，代价是 ；还有一类是回到 的，这类边就从当前层的 连到第 层的 ，不在当前层内部连接 和 。

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
#define N 420007 // 20000 * 21

#define ll long long

vector<pair<int, int> > e[N];
ll dis[N];
bool vis[N];
priority_queue<pair<ll, int> , vector<pair<ll, int> >, greater<pair<ll, int> > > Q;

void dij(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; Q.push(make_pair(0, s));
    while (!Q.empty()) {
        int u = Q.top().second; Q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [v, w] : e[u])
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push(make_pair(dis[v], v));
            }
    }
}

inline void add(int u, int v, int w) {
    e[u].push_back(make_pair(v, w));
}

int main() {
    int n = rd(), m = rd(), s = rd(), t = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(), w = rd();
        char c = getchar();
        for (; c != 'G' && c != 'B'; c = getchar()) ;
        for (int j = 0; j <= 20; ++j) {
            if (c == 'B')
                add(j * n + u, v, (w + (1 << j) - 1) / (1 << j));
            else
                add(j * n + u, j * n + v, (w  + (1 << j) - 1) / (1 << j));
        }
    }
    int p = rd();
    for (int i = 1; i <= p; ++i) {
        int x = rd(), c = rd();
        for (int j = 0; j < 20; ++j)
            add(j * n + x, (j + 1) * n + x, c);
    }
    dij(s);
    ll ans = 1e18;
    for (int i = 0; i <= 20; ++i) ans = min(ans, dis[i * n + t]);
    printf("%lld\n", ans == 1e18 ? -1 : ans);
    return 0;
}

arc061E

个点， 条边的图，每一条边有一个颜色。每次换一个颜色的边走需要 的代价，在同颜色里走不需要额外的代价。问从 号点走到 号点，最少需要的代价是多少。

思路：每个颜色一层。层之间的边代价为 ，内部的边代价为 。考虑层之间的边，需要给每两层的这个点连一条边，这样子会连 级别的边，这也太多了…… 换个方法，我们给每个点建立一个实点，让每一层的这个点，都连到这个实点上且代价为 （ 也可以，但是为了后面可以做 01 BFS ，这里就取代价为 ，最终结果再除 ）。考虑要开多大的点集合边集，点集： 个实点，每条边 个点，所以一共是 ；边集： 条边，最多有 个在层里面的点，所以边集大概是 。

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
#define N 100007
#define M 500007
 
unordered_map<int, int> id[N];
struct edge {int v, w, nxt;} e[2000007];
int hd[M], tot, totn, dis[M];
deque<int> Q;
bool vis[M];
 
inline void add(int u, int v, int w) {
    e[++tot].v = v; e[tot].w = w;
    e[tot].nxt = hd[u]; hd[u] = tot;
}
 
int main() {
    int n = rd(), m = rd();
    totn = n;
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(), c = rd();
        if (!id[u][c]) {id[u][c] = ++totn; add(u, totn, 1); add(totn, u, 1);}
        if (!id[v][c]) {id[v][c] = ++totn; add(v, totn, 1); add(totn, v, 1);}
        add(id[u][c], id[v][c], 0); add(id[v][c], id[u][c], 0);
    }
    memset(dis, 0x3f, sizeof(dis));
    Q.push_front(1); dis[1] = 0;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop_front();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = hd[u], v; i; i = e[i].nxt)
            if (dis[v = e[i].v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if (e[i].w) Q.push_back(v);
                else Q.push_front(v);
            }
    }
    printf("%d\n", dis[n] == dis[0] ? -1 : dis[n] / 2);
    return 0;
}

洛谷P1073

有 个点， 条边，有单向边也有双向边，每个点有个价格 ，在该点买入水晶需花费 ，卖掉水晶可以赚 。现有一个商人从 号点开始走，要走到 号点，可以重复经过城市，在旅行过程中，他最多可以买一次、卖一次。问他最多能赚到多少钱。

思路：以价格为边权建图，以买和卖两个动作分层。在图的内部边权都是 ，第 层到第 层之间的边代表买，所以边权是负数，第 层到第 层之间的边代表卖，所以便全是正的。因为要最大化赚到的钱，所以跑最长路。因为有负权边，所以不能用 dij 要用 spfa 。

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
#define N 300007

vector<pair<int, int> > e[N];
int dis[N], vis[N];
queue<int> Q;

void spfa(int s) {
    memset(dis, 0xcf, sizeof(dis));
    dis[s] = 0; Q.push(s);
    while (!Q.empty()) {
       int u = Q.front(); Q.pop(); vis[u] = 0;
       for (auto [v, w] : e[u])
           if (dis[v] < dis[u] + w) {
               dis[v] = dis[u] + w;
               if (!vis[v]) {Q.push(v); vis[v] = 1;}
           }
    }
}

inline void add(int u, int v, int w) {e[u].push_back(make_pair(v, w));}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) {
        int c = rd();
        add(i, n + i, -c);
        add(n + i, n * 2 + i, c);
    }
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(), z = rd();
        add(u, v, 0); add(n + u, n + v, 0); add(u + 2 * n, v + 2 * n, 0);
        if (z == 2) {add(v, u, 0); add(n + v, n + u, 0); add(v + 2 * n, u + 2 * n, 0);}
    }
    spfa(1);
    printf("%d\n", max(0, dis[2 * n + n]));
    return 0;
}

Floyd

求传递闭包

洛谷P2419

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
#define N 107
bool a[N][N];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd();
        a[u][v] = 1;
    }
    // floyd
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (a[i][k] && a[k][j]) a[i][j] = 1;
    // 统计有多少个点
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        bool f = 1;
        for (int j = 1; j <= n; ++j)
            if (i != j && !a[i][j] && !a[j][i])
             f = 0;
        if (f) cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}
  • Post title：最短路
  • Post author：Eva.Q
  • Create time：2022-07-03 10:21:51
  • Post link：https://qyy/2022/07/03/Algorithm/co-shortest-path/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.