比赛 hhh 评测结果 AAAAA
题目名称 最短路径问题 最终得分 100
用户昵称 雾茗 运行时间 0.012 s
代码语言 C++ 内存使用 0.39 MiB
提交时间 2018-07-31 10:05:55
显示代码纯文本
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cmath>
  4. #include<cstring>
  5. using namespace std;
  6. int a[101][3];
  7. double f[101][101];
  8. int n,i,j,k,x,y,m,s,e;
  9. int main()
  10. {
  11. freopen("short.in","r",stdin);
  12. freopen("short.out","w",stdout);
  13. cin >> n;
  14. for (i = 1; i <= n; i++)
  15. cin >> a[i][1] >> a[i][2];
  16. cin >> m;
  17. memset(f,0x7f,sizeof(f));
  18. for (i = 1; i <= m; i++)
  19. {
  20. cin >> x >> y;
  21. 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));
  22. }
  23. cin >> s >> e;
  24. for (k = 1; k <= n; k++)
  25. for (i = 1; i <= n; i++)
  26. for (j = 1; j <= n; j++)
  27. if ((i != j) && (i != k) && (j != k) && (f[i][k]+f[k][j] < f[i][j]))
  28. f[i][j] = f[i][k] + f[k][j];
  29. printf("%.2lf\n",f[s][e]);
  30. return 0;
  31. }