ons pre getchar spf n+2 ret read 短路径
★ 输入文件:
输出文件:
- short.in
简单对比 时间限制:1 s 内存限制:128 MB
- short.out
平面上有 n 个点(n<=100),每个点的坐标均在 - 10000~10000 之间。其中的一些点之间有连线。若有连线,则表示可从一个点到达另一个点,即两点间有通路,通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
输入文件为 short.in,共 n+m+3 行,其中:
第一行为整数 n。
第 2 行到第 n+1 行(共 n 行),每行两个整数 x 和 y,描述了一个点的坐标。
第 n+2 行为一个整数 m,表示图中连线的个数。
此后的 m 行,每行描述一条连线,由两个整数 i 和 j 组成,表示第 i 个点和第 j 个点之间有连线。
最后一行:两个整数 s 和 t,分别表示源点和目标点。
输出文件为 short.out,仅一行,一个实数(保留两位小数),表示从 s 到 t 的最短路径长度。
5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
3.41
- 1#include 2#include 3#include 4#include 5#include 6 7 using namespace std;
- 8 const int N = 101;
- 9 const int maxn = 999999;
- 10 11 int head[N];
- 12 double dis[N];
- 13 int vis[N];
- 14 int now = 1;
- 15 queue < int > q;
- 16 int m;
- 17 int n;
- 18 int s;
- 19 int e;
- 20 21 struct node {
- 22 double x,
- y;
- 23
- }
- D[N];
- 24 25 struct NODE {
- 26 int u,
- v,
- nxt;
- 27 double w;
- 28
- }
- E[N * 10];
- 29 30 void read(int & x) 31 {
- 32 char c = getchar();
- 33 x = 0;
- 34
- while (c < '0' || c > '9') c = getchar();
- 35
- while (c >= '0' && c <= '9') x = x * 10 + c - '0',
- c = getchar();
- 36
- }
- 37 38 double j(int u, int v) 39 {
- 40
- return sqrt(pow(abs(D[u].x - D[v].x), 2) + pow(abs(D[u].y - D[v].y), 2));
- 41
- }
- 42 43 void add(int u, int v, double w) 44 {
- 45 E[now].u = u;
- 46 E[now].v = v;
- 47 E[now].w = w;
- 48 E[now].nxt = head[u];
- 49 head[u] = now;
- 50 now++;
- 51
- }
- 52 53 void spfa(int s) 54 {
- 55
- for (int i = 1; i <= n; i++) 56 dis[i] = maxn;
- 57 dis[s] = 0;
- 58 vis[s] = 1;
- 59 q.push(s);
- 60
- while (!q.empty()) 61 {
- 62 int top = q.front();
- 63 q.pop();
- 64
- for (int i = head[top]; i != -1; i = E[i].nxt) 65 {
- 66 int v = E[i].v;
- 67 double w = E[i].w;
- 68
- if (dis[v] > dis[top] + w) 69 {
- 70 dis[v] = dis[top] + w;
- 71
- if (!vis[v]) 72 q.push(v);
- 73
- }
- 74
- }
- 75
- }
- 76 printf("%.2lf", dis[e]);
- 77
- return;
- 78
- }
- 79 80 int main() 81 {
- 82 freopen("short.in", "r", stdin);
- 83 freopen("short.out", "w", stdout);
- 84 read(n);
- 85
- for (int i = 1; i <= n; i++) 86 {
- 87 scanf("%lf%lf", &D[i].x, &D[i].y);
- 88 head[i] = -1;
- 89
- }
- 90 read(m);
- 91
- for (int i = 1; i <= m; i++) 92 {
- 93 int u,
- v;
- 94 read(u);
- 95 read(v);
- 96 double jl = j(u, v);
- 97 add(u, v, jl);
- 98 add(v, u, jl);
- 99
- }
- 100 101 read(s);
- read(e);
- 102 spfa(s);
- 103 104
- return 0;
- 105 106
- }
D 5 点
在我的机子上秒出,测试却超时了???
- 100-7185-2582
- 3377-6018
- 6566 9733
- 4144 721
- 9457 3504-3710-8589
- 185 931
- 9348 1363
- 8556-7689-3782-2807-6824-6695
- 3274 6059
- 1377-6754-4378 771
- 8509 412
- 7250 9219-1166-4786-9298 1549-4814 7236
- 6013-6454
- 9578-2953-6451 9629-8039 8751
- 481-6085-674 4185-4459 2803-7704-5280-8219-2524-8542-8397
- 1996-200-9432 756-3482 31
- 8848-7002-1938 9775
- 9541 5617-6699-1355-3057-3790
- 5876-1954
- 9062-5231
- 515 519
- 8112 4907-7046 8099-3965-9810
- 5346 8104
- 7222 6511-8157-184-4373 6420
- 4051 466-1524 6382-8981 3978
- 3728-7131-6513-9094-6496 8246-2962-6999
- 662 2372-6120 832
- 692 871
- 7926 7931
- 6149 5991
- 2851 9864-4228-8998-2161 1684-4484-5928
- 685 2210-6344 2541-7048-1458-2840 3552
- 6862 9285
- 1524 1969-1386 9891-8749-8493
- 7822 8571-6842-9967-2260 6214
- 9706-5038-4006-1262
- 4531-323
- 468 5335-2617-3056
- 71-8987-9365 213
- 5048-3088-5439-1213
- 6527-3206
- 3579 7760
- 9996 3175
- 635-1313-7607-8484-8086 1915-2507-4078-915-3495
- 9285-5225
- 1228 8694
- 8030 9760
- 3686 4826-1329 6688-4028 9699
- 6308-8406
- 5967 6256-1602 512
- 1000
- 63 38
- 42 82
- 70 35
- 53 8
- 19 38
- 51 46
- 10 33
- 51 61
- 20 29
- 34 16
- 11 71
- 29 66
- 83 15
- 18 71
- 84 52
- 57 8
- 59 75
- 45 11
- 8 31
- 89 73
- 78 99
- 32 85
- 7 89
- 43 95
- 5 52
- 2 12
- 30 39
- 18 92
- 98 66
- 57 77
- 38 58
- 83 76
- 72 74
- 21 10
- 97 61
- 14 52
- 74 63
- 23 47
- 79 96
- 87 87
- 55 65
- 53 68
- 68 75
- 33 70
- 63 78
- 62 23
- 72 37
- 43 54
- 23 20
- 25 34
- 41 39
- 33 66
- 45 9
- 57 79
- 92 81
- 63 19
- 15 81
- 86 62
- 42 60
- 15 83
- 16 33
- 83 54
- 42 60
- 24 57
- 32 2
- 49 31
- 22 63
- 68 6
- 81 74
- 53 72
- 43 7
- 14 92
- 32 20
- 36 63
- 49 58
- 15 80
- 48 72
- 61 60
- 32 27
- 74 22
- 22 20
- 23 45
- 100 11
- 54 31
- 23 52
- 23 64
- 52 66
- 46 30
- 53 9
- 81 40
- 59 13
- 1 82
- 2 92
- 24 73
- 50 76
- 9 8
- 15 81
- 20 16
- 8 47
- 38 74
- 65 95
- 64 35
- 67 87
- 30 73
- 28 85
- 34 55
- 21 55
- 52 81
- 71 52
- 93 75
- 34 74
- 5 91
- 38 98
- 47 78
- 59 14
- 83 35
- 50 14
- 65 14
- 63 27
- 1 86
- 8 90
- 51 64
- 60 95
- 64 38
- 100 63
- 74 90
- 45 21
- 4 69
- 17 94
- 54 63
- 39 41
- 68 86
- 76 77
- 2 73
- 40 80
- 59 50
- 47 76
- 23 20
- 77 28
- 46 85
- 87 99
- 63 88
- 73 51
- 14 61
- 81 99
- 27 94
- 15 38
- 81 70
- 89 8
- 43 30
- 27 71
- 67 70
- 97 100
- 83 73
- 50 29
- 21 24
- 79 88
- 47 85
- 35 32
- 5 5
- 60 51
- 95 94
- 28 100
- 29 98
- 89 93
- 41 48
- 76 57
- 51 69
- 16 31
- 2 64
- 34 60
- 25 27
- 77 19
- 99 43
- 71 62
- 9 60
- 86 96
- 22 77
- 94 1
- 30 53
- 26 72
- 42 37
- 70 29
- 4 91
- 60 43
- 91 33
- 59 63
- 10 39
- 33 36
- 85 66
- 51 74
- 27 5
- 91 86
- 13 56
- 8 3
- 18 89
- 3 44
- 79 49
- 14 12
- 80 100
- 88 18
- 99 14
- 34 63
- 41 70
- 48 43
- 56 8
- 71 32
- 20 40
- 11 83
- 12 37
- 42 45
- 40 28
- 75 66
- 73 85
- 43 61
- 99 81
- 62 45
- 13 36
- 41 70
- 97 6
- 79 100
- 55 65
- 53 34
- 14 84
- 82 56
- 2 22
- 42 53
- 56 64
- 45 53
- 37 89
- 18 65
- 45 38
- 42 24
- 63 23
- 43 73
- 71 99
- 31 26
- 12 79
- 45 11
- 1 77
- 41 83
- 5 8
- 33 35
- 43 61
- 71 78
- 70 50
- 24 47
- 64 98
- 94 60
- 13 97
- 76 47
- 70 74
- 63 97
- 47 37
- 22 27
- 34 80
- 29 48
- 82 88
- 15 82
- 89 54
- 63 71
- 63 5
- 76 61
- 70 5
- 81 67
- 70 71
- 55 49
- 17 26
- 82 49
- 70 73
- 87 77
- 33 74
- 86 42
- 33 50
- 65 65
- 98 46
- 79 20
- 94 32
- 13 95
- 36 26
- 71 66
- 78 57
- 69 18
- 46 18
- 51 73
- 79 64
- 67 91
- 80 59
- 54 68
- 97 77
- 37 41
- 87 13
- 32 71
- 31 59
- 3 69
- 3 46
- 32 86
- 21 61
- 85 77
- 6 86
- 82 18
- 60 35
- 17 30
- 22 57
- 79 32
- 53 47
- 62 49
- 88 99
- 85 28
- 29 57
- 38 37
- 76 73
- 35 64
- 21 83
- 48 31
- 63 36
- 39 94
- 91 54
- 20 89
- 70 9
- 5 51
- 17 36
- 46 11
- 47 21
- 53 54
- 36 41
- 38 85
- 20 32
- 49 45
- 41 20
- 77 68
- 92 42
- 38 64
- 36 34
- 82 96
- 98 78
- 80 48
- 46 10
- 73 31
- 23 64
- 2 66
- 86 73
- 49 32
- 70 71
- 50 82
- 81 64
- 69 58
- 86 51
- 45 54
- 50 37
- 38 11
- 45 45
- 52 56
- 36 37
- 1 97
- 90 83
- 50 43
- 3 62
- 44 29
- 20 58
- 10 36
- 82 2
- 97 56
- 50 78
- 79 43
- 76 65
- 50 27
- 16 13
- 72 13
- 20 74
- 69 77
- 35 7
- 67 20
- 99 58
- 23 60
- 30 79
- 7 74
- 21 17
- 11 98
- 5 12
- 12 71
- 47 69
- 5 69
- 76 6
- 93 67
- 73 77
- 89 26
- 61 30
- 73 89
- 78 60
- 11 44
- 25 44
- 17 73
- 18 87
- 38 3
- 84 8
- 64 34
- 84 45
- 18 97
- 56 66
- 67 72
- 6 96
- 51 79
- 83 21
- 42 1
- 29 11
- 61 30
- 94 81
- 21 16
- 30 84
- 79 74
- 35 93
- 9 88
- 98 33
- 29 3
- 53 57
- 49 92
- 72 78
- 20 54
- 31 16
- 98 66
- 34 99
- 52 2
- 87 37
- 99 96
- 52 77
- 15 94
- 20 66
- 72 45
- 88 20
- 5 10
- 25 62
- 96 98
- 62 63
- 41 52
- 50 23
- 15 48
- 61 57
- 91 74
- 21 83
- 34 12
- 19 29
- 2 33
- 16 93
- 29 75
- 45 36
- 41 75
- 96 86
- 67 67
- 5 88
- 31 59
- 98 21
- 23 72
- 69 65
- 7 96
- 78 7
- 9 71
- 7 100
- 73 39
- 11 14
- 9 5
- 44 57
- 57 90
- 52 54
- 21 85
- 69 85
- 87 40
- 46 57
- 99 21
- 5 47
- 62 49
- 1 20
- 10 89
- 28 44
- 36 48
- 12 36
- 92 23
- 53 7
- 100 75
- 46 9
- 19 48
- 63 79
- 81 45
- 81 50
- 74 34
- 5 72
- 40 47
- 98 50
- 24 88
- 36 10
- 77 74
- 35 38
- 8 71
- 29 52
- 43 88
- 93 17
- 25 57
- 34 94
- 63 8
- 3 89
- 30 9
- 95 56
- 53 37
- 42 49
- 40 99
- 20 44
- 58 18
- 12 69
- 41 51
- 15 5
- 88 16
- 72 64
- 2 21
- 68 48
- 57 43
- 27 33
- 1 100
- 90 58
- 39 99
- 71 86
- 49 61
- 13 86
- 19 60
- 92 49
- 24 23
- 47 24
- 60 81
- 28 55
- 17 58
- 90 53
- 67 49
- 80 12
- 72 22
- 92 84
- 64 46
- 83 53
- 41 21
- 83 71
- 75 65
- 33 68
- 45 4
- 47 11
- 13 37
- 67 17
- 38 94
- 64 17
- 70 6
- 6 26
- 79 45
- 96 85
- 18 23
- 46 61
- 10 32
- 39 31
- 18 80
- 11 84
- 39 67
- 27 15
- 27 70
- 62 95
- 32 61
- 93 44
- 22 78
- 61 44
- 11 99
- 81 57
- 21 8
- 86 41
- 51 56
- 29 91
- 16 37
- 13 30
- 96 47
- 90 30
- 9 1
- 49 56
- 72 1
- 19 33
- 55 13
- 15 8
- 7 69
- 21 41
- 17 13
- 97 45
- 61 64
- 40 73
- 14 47
- 44 4
- 58 34
- 24 96
- 90 81
- 27 87
- 30 62
- 24 78
- 78 39
- 53 27
- 60 100
- 73 24
- 77 81
- 35 45
- 37 33
- 98 94
- 35 8
- 18 79
- 15 76
- 9 96
- 31 96
- 60 95
- 78 2
- 29 68
- 74 68
- 75 83
- 11 95
- 87 39
- 99 88
- 23 34
- 79 49
- 68 66
- 76 96
- 67 96
- 12 80
- 15 60
- 18 65
- 76 8
- 93 83
- 92 89
- 6 96
- 91 28
- 56 14
- 1 62
- 8 46
- 45 25
- 89 5
- 52 96
- 12 74
- 36 65
- 44 9
- 97 64
- 64 37
- 68 74
- 51 79
- 13 20
- 12 1
- 31 83
- 40 74
- 42 17
- 54 95
- 49 49
- 69 1
- 96 88
- 94 86
- 84 69
- 58 85
- 4 27
- 8 97
- 92 62
- 32 69
- 28 37
- 6 43
- 33 40
- 62 51
- 27 70
- 15 11
- 49 62
- 23 48
- 80 39
- 51 60
- 84 60
- 53 88
- 70 15
- 15 62
- 67 58
- 14 41
- 15 11
- 80 66
- 54 62
- 70 80
- 59 37
- 95 2
- 23 36
- 58 61
- 27 42
- 87 4
- 22 61
- 78 55
- 21 40
- 78 80
- 78 73
- 81 92
- 89 7
- 1 96
- 63 81
- 65 50
- 34 75
- 24 8
- 12 65
- 80 65
- 95 87
- 83 13
- 99 64
- 34 81
- 70 57
- 17 34
- 73 36
- 14 24
- 4 88
- 14 42
- 42 99
- 99 12
- 35 87
- 61 4
- 20 64
- 98 93
- 85 58
- 96 60
- 32 33
- 76 20
- 19 68
- 75 39
- 65 95
- 98 49
- 56 9
- 39 97
- 88 92
- 77 72
- 34 25
- 88 96
- 18 67
- 24 85
- 35 33
- 61 6
- 49 1
- 7 83
- 61 21
- 27 42
- 31 22
- 21 85
- 76 23
- 75 34
- 14 1
- 54 95
- 93 81
- 16 22
- 39 29
- 69 88
- 22 88
- 88 90
- 92 71
- 85 38
- 77 7
- 69 25
- 10 5
- 70 60
- 37 76
- 94 11
- 43 42
- 37 3
- 61 96
- 82 55
- 81 26
- 46 59
- 62 92
- 65 36
- 21 18
- 16 11
- 37 63
- 28 100
- 7 55
- 34 9
- 50 13
- 48 70
- 16 97
- 84 78
- 80 55
- 49 100
- 4 53
- 72 62
- 12 10
- 56 53
- 5 86
- 60 87
- 99 73
- 54 14
- 91 3
- 4 73
- 64 69
- 63 32
- 86 22
- 6 57
- 76 89
- 8 93
- 35 26
- 63 66
- 66 4
- 100 28
- 30 90
- 28 9
- 12 65
- 27 46
- 95 100
- 73 3
- 69 80
- 44 4
- 20 42
- 64 37
- 68 73
- 75 7
- 64 80
- 37 53
- 58 29
- 16 35
- 97 15
- 82 75
- 13 13
- 52 8
- 15 17
- 35 58
- 94 73
- 71 75
- 1 51
- 71 70
- 63 29
- 93 44
- 44 74
- 14 8
- 60 37
- 96 29
- 18 16
- 37 44
- 29 34
- 59 44
- 12 46
- 85 3
- 4 72
- 100 17
- 22 16
- 93 69
- 56 23
- 31 39
- 93 82
- 16 27
- 84 73
- 11 47
- 21 18
- 58 32
- 74 94
- 6 32
- 12 99
- 22 13
- 8 97
- 65 83
- 95 71
- 46 4
- 33 67
- 87 63
- 93 3
- 65 13
- 81 80
- 7 11
- 47 18
- 63 11
- 53 1
- 79 82
- 2 8
- 43 67
- 49 61
- 76 11
- 43 23
- 98 1
- 66 17
- 83 16
- 90 54
- 86 75
- 41 95
- 7 24
- 53 83
- 19 13
- 60 11
- 89 37
- 37 25
- 49 57
- 13 75
- 19 22
- 3 49
- 68 46
- 20 76
- 68 33
- 94 72
- 6 32
- 93 50
- 12 73
- 9 47
- 48 27
- 76 23
- 72 74
- 32 24
- 43 80
- 24 44
- 58 17
- 27 95
- 27 82
- 46 93
- 19 82
- 80 16
- 52 11
- 5 73
- 98 27
- 97 19
- 21 100
- 75 82
- 93 1
- 70 98
- 27 39
- 42 67
- 32 83
- 82 78
- 98 8
- 85 59
- 37 62
- 84 64
- 53 45
- 85 87
- 17 38
- 17 76
- 62 36
- 15 80
- 44 59
- 95 60
- 6 49
- 72 42
- 57 88
- 48 85
- 55 85
- 67 13
- 53 7
- 11 14
- 41 76
- 77 11
- 99 41
- 80 64
- 46 98
- 47 53
- 41 22
- 17 44
- 88 29
- 52 59
- 26 84
- 18 75
- 24 28
- 12 40
- 21 82
- 25 86
- 47 53
- 68 58
- 50 54
- 12 2
- 98 6
- 10 81
- 29 99
- 10 5
- 81 8
- 63 4
- 8 4
- 100 74
- 83 11
- 28 67
- 23 86
- 58 19
- 6 34
- 82 38
- 53 76
- 53 79
- 98 38
- 32 91
- 77 29
- 9 16
- 93 23
- 23 60
- 49 66
- 17 83
- 60 66
- 12 69
- 70 51
- 3 72
- 53 85
- 82 53
- 67 93
- 58 51
- 75 30
- 28 55
- 83 84
- 18 72
- 37 18
- 92 2
- 73 69
- 5 68
- 35 84
- 51 65
- 95 39
- 19 26
- 26 77
answer
16466.66
cogs 1075. [省常中 2011S4] 最短路径问题
来源: http://www.bubuko.com/infodetail-2074484.html