首页 > 代码库 > cogs 1075. [省常中2011S4] 最短路径问题

cogs 1075. [省常中2011S4] 最短路径问题

★   输入文件:short.in   输出文件:short.out   简单对比
时间限制:1 s   内存限制:128 MB

 [问题描述] 

平面上有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<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cmath>
  5 #include<queue>
  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] 最短路径问题