Shortest Path
Eva.Q Lv9
2022-03-15 05:34:51

继续跑图~

Dijstra的缺点

不支持负权边, 单源

Floyd

支持负权边、多源、可求最长路

几百

任意两个点之间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n = rd(), m = rd();

for (int i = 1; i <= n; ++i) {
    e[i].u = rd(); e[i].v = rd();
}

for (int k = 1; k <= n; ++k) { //枚举中间过渡点
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (dis[i][j] > dis[i][k] + dis[k][j])
                dis[i][j] = dis[i][k] + dis[k][j];
        }
    }
}

Bellman-Ford

几千

遍历所有的边

1
2
3
4
5
6
for (int k = 1; k <= n - 1; ++k) {//
    for (int i = 1; i <= m; ++i) {//第i条边 起点：u[i] 终点：v[i]
        if (dis[v[i]] > dis[u[i]] + w[i])
            dis[v[i]] = dis[u[i]] + w[i];
    }
}

因为任意两个点之间的最短路，最多有 条边，所以只需要松弛 次

检测负环

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int k = 1; k <= n - 1; ++k) {//
    for (int i = 1; i <= m; ++i) {//第i条边 起点：u[i] 终点：v[i]
        if (dis[v[i]] > dis[u[i]] + w[i])
            dis[v[i]] = dis[u[i]] + w[i];
    }
}

int f = 0;
for (int i = 1; i <= m; ++i) {
    if (dis[v[i]] > dis[u[i]] + w[i]) f = 1;
}

if (f) cout << "There is a negative circle" << endl;

SPFA Bellman-Ford的队列优化

是一个常数，在稀疏图中 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
queue<int> q;

int start = rd();
q.push(start);
dis[start] = 0;
vis[start] = 1;
while (!q.empty()) {
    int x = q.front();
    q.pop(); vis[x] = 0;
    for (int i = hd[x]; i; i = next[i]) {
        int y = v[i];
        if (dis[y] > dis[x] + w[i]) {
            dis[y] > dis[x] + w[i];
            if (!vis[y]) {vis[y] = 1; q.push(y);}
        }
    }
}

几种最短路算法比较

Dijkstra ：效率高；不能处理负边权

FLoyd ：效率低；能处理负权边，可求最长路，好写

Bellman-Ford ：效率中等；能处理负权边

字符串与数字的映射

1
2
3
4
5
6
7
8
9
10
map<string, int> ml;
string s;
for (int i = 1; i <= n; ++i) {cin >> s; ml[s] = i;}
int m; cin >> m;
while (m--) {
    cin >> s; temp1 = ml[s];
    cin >> num;
    cin >> s; temp2 = ml[s];
    dis[temp1][temp2] = num;
}

垃圾作业

第一题 六度分离

问任意两个点是否都能找到一个长度不大于 ​ 的路径

这是一个多源最短路问题

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
#include<bits/stdc++.h>
#define N 107
#define M 207
using namespace std;

inline int rd() {
    bool f = 0;
    int x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int n, m, dis[N][N];

void work() {
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= n; ++i) {
        dis[i][i] = 0;
    }
    for (int i = 1; i <= m; ++i) {
        int u = rd() + 1, v = rd() + 1;
        dis[u][v] = 1; dis[v][u] = 1;
    }
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dis[i][j] > dis[i][k] + dis[k][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (dis[i][j] > 7) {puts("No"); return;}
        }
    }
    puts("Yes");
}

int main() {
    while (cin >> n >> m) work();
    return 0;
}

第二题 我要去Colin家玩儿

我要去colin家玩儿，我有好多个开始车站可以选择， 但我要去的地方只有colin家——沧州，我最少花费多少呢？

我疯狂 wa 还有 TLE ，colin 知道了他说：你蠢不蠢，不会以我家为起点吗？

我：哦哦哦

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
#include<bits/stdc++.h>
#define N 1007
#define M 20007
#define ll long long
using namespace std;

inline int rd() {
    bool f = 0;
    int x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

struct edge{
    int v, w, nxt;
}e[M];

int tot, vis[N], hd[N], dis[N];

void add(int u, int v, int w) {
    e[++tot].v = v; e[tot].w = w;
    e[tot].nxt = hd[u];
    hd[u] = tot;
}

queue<int> q;
int n, m, s;

void spfa(int x) {
    for (int i = 1; i <= n; ++i) {
        dis[i] = 999999999; vis[i] = 0;
    }
    q.push(x); dis[x] = 0; vis[s] = 1;
    while(!q.empty()) {
        int t = q.front();
        q.pop(); vis[t] = 0;
        for (int i = hd[t]; i; i = e[i].nxt) {
            int y = e[i].v;
            if (dis[y] > dis[t] + e[i].w) {
                dis[y] = dis[t] + e[i].w;
                if (!vis[y]) {vis[y] = 1; q.push(y);}
            }
        }
    }
}

void work() {
    tot = 0;
    for (int i = 1; i <= n; ++i) hd[i] = 0;
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(), w = rd();
        add(v, u, w);
    }
    int a = rd(), ans = 999999999;
    spfa(s);
    for (int i = 1; i <= a; ++i) {
        int t = rd();
        ans = min(ans, dis[t]);
    }
    if (ans == 999999999) puts("-1");
    else cout << ans << endl;
}

int main() {
    while (cin >> n >> m >> s) work();
    return 0;
}

第三题 骗钱行为

问存不存在一种货币，它通过其他货币汇率转换后，自己的价值会变高。这就是著名的套利 (Arbitrage) 。

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
#include<bits/stdc++.h>
using namespace std;
#define N 37
#define M 2007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int n, m, vis[N], hd[N], tot;
double dis[N][N];
map<string, int> ml;
string s;
queue<int> q;

struct edge{
    int v, nxt;
    double w;
}e[M];

void add(int u, int v, int w) {
    e[++tot].v = v; e[tot].w = w;
    e[tot].nxt = hd[u];
    hd[u] = tot;
}

void work() {
    tot = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j) {
                dis[i][i] = 1; vis[i] = 0; hd[i] = 0;
                cin >> s; ml[s] = i;
            }else dis[i][j] = 0;
        }
    }
    m = rd();
    for (int i = 1; i <= m; ++i) {
        int temp1, temp2;
        double num;
        cin >> s; temp1 = ml[s];
        cin >> num;
        cin >> s; temp2 = ml[s];
        dis[temp1][temp2] = num;
        add(temp1, temp2, num);
    }
    for (int k = 1; k <= n; ++k) { //枚举中间过渡点
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dis[i][j] < dis[i][k] * dis[k][j])
                    dis[i][j] = dis[i][k] * dis[k][j];
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        if (dis[i][i] > 1) {
            puts("Yes"); return;
        }
    puts("No");
}

int main() {
    int i = 1;
    while(cin >> n && n != 0) {printf("Case %d: ", i++); work();}
    return 0
}
  • Post title：Shortest Path
  • Post author：Eva.Q
  • Create time：2022-03-15 05:34:51
  • Post link：https://qyy/2022/03/15/Algorithm/Shortest Path/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.