首页 > 代码库 > 洛谷 P1744 采购特价商品
洛谷 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：
50 02 02 20 23 151 21 31 42 53 51 5
输出样例#1：
3.41
说明
100%数据：n<=100，m<=1000
spfa模板题
屠龙宝刀点击就送
#include <cstdio>#include <cmath>#include <queue>using namespace std;struct node{ int next,to; double dis;}edge[10001];bool vis[101];double dis[101];int tot,i,j,n,m,x[101],y[101],head[10001];inline void add_edge(int u,int v,double farr){ edge[++tot].next=head[u]; edge[tot].to=v; edge[tot].dis=farr; head[u]=tot;}void spfa(int start){ queue<int>q; for(i=1;i<=n;++i) { dis[i]=1e9; vis[i]=0; } dis[start]=0; vis[start]=1; q.push(start); while(!q.empty()) { int tope=q.front(); q.pop(); vis[tope]=0; for(i=head[tope];i;i=edge[i].next) { int to=edge[i].to; if(dis[to]>dis[tope]+edge[i].dis) { dis[to]=dis[tope]+edge[i].dis; if(!vis[to]) { q.push(to); vis[to]=1; } } } }}int main(){ scanf("%d",&n); for(i=1;i<=n;++i) scanf("%d%d",&x[i],&y[i]); int from,to; scanf("%d",&m); while(m--) { scanf("%d%d",&from,&to); add_edge(from,to,sqrt((x[from]-x[to])*(x[from]-x[to])+(y[from]-y[to])*(y[from]-y[to]))); add_edge(to,from,sqrt((x[from]-x[to])*(x[from]-x[to])+(y[from]-y[to])*(y[from]-y[to]))); } int s,t; scanf("%d%d",&s,&t); spfa(s); printf("%.2lf",dis[t]); return 0;}
洛谷 P1744 采购特价商品
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。