kuangbin最短路专题

ACM

最短路专题

kuangbin带你飞专题4最短路

A

一个很裸的最短路问题，但是我又又又被卡了好久啊。
因为可能会有重边，而且数据读入的顺序和我平时的顺序不太一样，导致一直被卡。。。

B

是一个完全图，最后特别要注意一个东西！
printf() 函数中不存在 %lf ，输入 double 用 %lf 输出用 %f
输出格式害人一直以为的东西竟然是错的emmm

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 205;
double dis[maxn];
double G[maxn][maxn];
struct Node{
    int x, y;
}point[maxn];
int n;
double cal(int x1, int y1, int x2, int y2){
    return sqrt(1.0*(x1-x2)*(x1-x2)+1.0*(y1-y2)*(y1-y2));
}
const double INF = 1e9;
typedef pair<double, int> P;
void dijk(){
    for(int i=0; i<n; i++) dis[i] = INF;
    int s = 0;
    dis[s] = 0;
    priority_queue<P, vector<P>, greater<P> > pq;
    pq.push(P(0, s));
    while(!pq.empty()){
        P temp = pq.top();
        pq.pop();
        int u = temp.second;
        if(dis[u]<temp.first) continue;
        for(int i=0; i<n; i++){
            if(dis[i]>max(dis[u], G[u][i])){
                dis[i] = max(dis[u], G[u][i]);
                pq.push(P(dis[i], i));
            }
        }
    }
    printf("Frog Distance = %.3f\n\n", dis[1]);
}
int main(){
    int kase = 0;
     while(~scanf("%d", &n)&&n){
        int x, y;
        for(int i=0; i<n; i++){
            scanf("%d%d", &point[i].x, &point[i].y);
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<i; j++){
                if(i == j) G[i][j] = 0;
                else {
                    G[i][j] = cal(point[i].x, point[i].y, point[j].x, point[j].y);
                    G[j][i] = G[i][j];
                }
            }
        }
        printf("Scenario #%d\n", ++kase);
        dijk();
     }
    return 0;
}

c

要求找到一个路径从1到n，使得这条路径上的最小的边权最大
还是用不断的拓展的思想，每次用最大的边进行拓展，所以优先队列用less<P>, 然后注意dis[]的初始化，应该还是比较的简单的。
关键就是不断拓展的思想

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e3+10;
struct Node{
    int v, weight;
};
vector<Node> G[maxn];
int n, m;
typedef pair<int, int> P;
int dis[maxn];
const int INF = 1e9;
void dijk(int s){
    for(int i=0; i<maxn; i++) dis[i] = -1;
    priority_queue<P, vector<P>, less<P> > pq;
    pq.push(P(0, s));
    dis[s] = INF;
    while(!pq.empty()){
        P temp = pq.top();
        pq.pop();
        int u = temp.second;
        if(temp.first>dis[u]) continue;
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i].v;
            int weight = G[u][i].weight;
            if(dis[v]<min(dis[u], weight)){
                dis[v] = min(dis[u], weight);
                pq.push(P(dis[v], v));
            }
        }
    }
    return;
}
int main()
{
    int t;
    scanf("%d", &t);
    int kase = 1;
    while(t--){
        scanf("%d%d", &n, &m);
        for(int i=0; i<maxn; i++) G[i].clear();
        for(int i=0; i<m; i++){
            int u, v, weight;
            scanf("%d%d%d", &u, &v, &weight);
            G[u].push_back(Node{v, weight});
            G[v].push_back(Node{u, weight});
        }
        printf("Scenario #%d:\n", kase++);
        dijk(1);
        printf("%d\n\n", dis[n]);
    }
    return 0;
}

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
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 1e3+10;
struct Edge{
    int v, weight;
};
typedef pair<int, int> P;
vector<Edge> G1[maxn];
vector<Edge> G2[maxn];
int dis1[maxn];
int dis2[maxn];
const int INF = 1e9;
int n, m, x;
void dijk(vector<Edge> *G, int *dis){
    for(int i=0; i<=n; i++) dis[i] = INF;
    dis[x] = 0;
    priority_queue<P, vector<P>, greater<P> > pq;
    pq.push(P(0, x));
    while(!pq.empty()){
        P temp = pq.top();
        pq.pop();
        int u = temp.second;
        if(temp.first>dis[u]) continue;
        for(int i=0; i<G[u].size(); i++){
            int v = G[u][i].v;
            int weight = G[u][i].weight;
            if(dis[v]>dis[u]+weight){
                dis[v] = dis[u]+weight;
                pq.push(P(dis[v], v));
            }
        }
    }
    return;
}
int main()
{
    while(~scanf("%d%d%d", &n, &m, &x)){
        int u, v, weight;
        for(int i=0; i<maxn; i++){
            G1[i].clear();
            G2[i].clear();
        }
        for(int i=0; i<m; i++){
            scanf("%d%d%d", &u, &v, &weight);
            G1[u].push_back(Edge{v, weight});
            G2[v].push_back(Edge{u, weight});
        }
        dijk(G2, dis2);
        dijk(G1, dis1);
        int ans = -1;
        for(int i=1; i<=n; i++){
            if(i == x) continue;
            else ans = max(ans, dis1[i]+dis2[i]);
            //printf("%d %d %d\n", i, dis1[i], dis2[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

未解决的问题

本文标题:kuangbin最短路专题

文章作者:Babydragon

发布时间:2018-04-17, 15:42:47

最后更新:2018-04-18, 14:13:19

原始链接:http://baolintian.github.io/2018/04/17/kuangbin最短路专题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. A
  2. 2. B
  3. 3. c
  4. 4. D
  5. 5. 未解决的问题
{{ live2d() }}