P1744 采购特价商品

题目背景

《爱与愁的故事第三弹·shopping》第一章。

题目描述

中山路店山店海,成了购物狂爱与愁大神的“不归之路”。中山路上有n(n<=100)家店,每家店的坐标均在-10000~10000之间。其中的m家店之间有通路。若有通路,则表示可以从一家店走到另一家店,通路的距离为两点间的直线距离。现在爱与愁大神要找出从一家店到另一家店之间的最短距离。你能帮爱与愁大神算出吗?

输入输出格式

输入格式:

共n+m+3行:

第1行:整数n

第2行~第n+1行:每行两个整数x和y,描述了一家店的坐标

第n+2行:整数m

第n+3行~第n+m+2行:每行描述一条通路,由两个整数i和j组成,表示第i家店和第j家店之间有通路。

第n+m+3行:两个整数s和t,分别表示原点和目标店

输出格式:

仅一行:一个实数(保留两位小数),表示从s到t的最短路径长度。

输入输出样例

输入样例#1: 复制

5
0 0
2 0
2 2
0 2
3 1
5
1 2
1 3
1 4
2 5
3 5
1 5
输出样例#1: 复制

3.41

说明

100%数据:n<=100,m<=1000

floyd

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 101
#define maxn 999999
using namespace std;
double f[N][N];
int n,m,s,t,a,b,tot,x[N],y[N];
int read()
{
    ,f=; char ch=getchar();
    ;ch=getchar();}
    +ch-',ch=getchar();
    return x*f;
}
int main()
{
    n=read();
    ;i<=n;i++)
     x[i]=read(),y[i]=read();
    ;i<=n;i++)
     ;j<=n;j++)
      f[i][j]=maxn;
    m=read();
    ;i<=m;i++)
    {
        a=read(),b=read();
        f[a][b]=sqrt(pow(x[a]-x[b],)+pow(y[a]-y[b],));
        f[b][a]=sqrt(pow(x[a]-x[b],)+pow(y[a]-y[b],));
    }
    ;k<=n;k++)
     ;i<=n;i++)
      ;j<=n;j++)
       f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
    a=read(),b=read();
    printf("%.2lf",f[a][b]);
    ;
}

最新文章

  1. hadoop安装遇到的各种异常及解决办法
  2. 【python游戏编程之旅】第四篇---pygame中加载位图与常用的数学函数。
  3. Android开发之Android Context,上下文(Activity Context, Application Context)
  4. php 正则校验是否是域名
  5. mysql中varchar最长多少
  6. 将DataTable 存到一个集合当中
  7. DARK的锁链
  8. 浅谈移动端rem的用法
  9. 入坑以来最清晰的this指南[老哥们来交流指正]
  10. OpenCV 之 网络摄像头
  11. JS分号 惹的坑
  12. Graph Cuts学习笔记2014.5.16----1
  13. 使用bootstrap的dropdown部件时报错:error:Bootstrap dropdown require Popper.js
  14. C#应用NPOI实现导出EXcel表格中插入饼状图(可实现动态数据生成)
  15. Maven整合SSM测试
  16. 基于zepto的移动端轻量级日期插件
  17. Spring框架学习
  18. python零碎知识点
  19. SpringBoot中动态加载(热部署)
  20. (转)Java程序员应该知道的10个调试技巧

热门文章

  1. 动态规划:区间DP与环形DP
  2. centOS 安装Python3与python2并存
  3. Enterprise Architect 13 : 需求建模 自动命名并计数
  4. 验证组件——FluentValidation
  5. 「6月雅礼集训 2017 Day11」delight
  6. Docker explainations
  7. 记一次Node项目的优化
  8. End to End Sequence Labeling via Bidirectional LSTM-CNNs-CRF论文小结
  9. Java 将html导出word格式
  10. Tomcat8配置默认项目