比赛 |
hhh |
评测结果 |
AAAAA |
题目名称 |
最短路径问题 |
最终得分 |
100 |
用户昵称 |
雾茗 |
运行时间 |
0.012 s |
代码语言 |
C++ |
内存使用 |
0.39 MiB |
提交时间 |
2018-07-31 10:05:55 |
显示代码纯文本
- #include<cstdio>
- #include<iostream>
- #include<cmath>
- #include<cstring>
- using namespace std;
- int a[101][3];
- double f[101][101];
- int n,i,j,k,x,y,m,s,e;
- int main()
- {
- freopen("short.in","r",stdin);
- freopen("short.out","w",stdout);
- cin >> n;
- for (i = 1; i <= n; i++)
- cin >> a[i][1] >> a[i][2];
- cin >> m;
- memset(f,0x7f,sizeof(f));
- for (i = 1; i <= m; i++)
- {
- cin >> x >> y;
- f[y][x] = f[x][y] = sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));
- }
- cin >> s >> e;
- for (k = 1; k <= n; k++)
- for (i = 1; i <= n; i++)
- for (j = 1; j <= n; j++)
- if ((i != j) && (i != k) && (j != k) && (f[i][k]+f[k][j] < f[i][j]))
- f[i][j] = f[i][k] + f[k][j];
- printf("%.2lf\n",f[s][e]);
- return 0;
- }