kuangbin最短路专题

最短路专题

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;
}

未解决的问题

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