【FZYZOJ】下片 题解(最短路+超级源点)
2024-09-07 17:32:12
题目描述
为了提高服务器的耐受能力,很多流量大的网站都会架设多台服务器,而互联网的路由能找到线路最短的一台服务器。 现在UOI想要下片,他有好多台电脑,又有好多服务器可以提供下载。UOI将给你一个网络图,告诉你点点之间的线路长度,问最短的线路长是多少,以及选择的那台用来下载的电脑和被选的服务器的编号。 如果有多台电脑/服务器之间连线都是最短线路,输出电脑编号最小的;如果还有多种选择,输出服务器编号最小的。
输入格式
第一行n,m,表示总格有n个点,m条网络连线 接下来m行,表示每条网络连线所连接的A、B点和线的长度。 接下来一个数T1,表示UOI有多少台电脑。 下一行T1个数,表示UOI每台电脑的编号。 接下来一个数T2,表示有多少台服务器。 下一行T2个数,表示每台服务器编号。
输出格式
三个数,分别是线路长度,UOI下载用的电脑,提供片的下载源
-------------------------------------------------------------------------------------------------------------------------
题意转化:给你一些源点和一些汇点,求一条连接源点和汇点的路径并且使得这条路径的长度最小。
使用n次spfa显然会TLE。这时候我们要引入一个概念:超级源点。意思是引入一个0号点,能连接所有源点,并且不影响原图,即长度为0。这样跑1次spfa就够。此题还要求输出源点和汇点,我们开一个pre数组,记录每个点的前驱即可(前驱指的是从哪个源点可以到达那里)。
代码中稍稍做了一点修改,本身思路与其相符。
#include<bits/stdc++.h>
using namespace std;
queue<int> q;
struct node
{
int to,dis;
};
vector<node> v[];
int n,m,t1,t2,a[],vis[],pre[];
long long ans=,dis[];
int ans1,ans2;
int main()
{
memset(dis,0x3f,sizeof(dis));
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++)
{
int u,to,d;
scanf("%d%d%d",&u,&to,&d);
v[u].push_back((node){to,d});
v[to].push_back((node){u,d});
}
scanf("%d",&t1);
for (int i=;i<=t1;i++) scanf("%d",&a[i]);
sort(a+,a+t1+);
scanf("%d",&t2);
int t;
for (int i=;i<=t2;i++) scanf("%d",&t),pre[t]=t,vis[t]=,dis[t]=,q.push(t);
while(!q.empty())
{
int now=q.front();q.pop();vis[now]=;
for (int i=;i<v[now].size();i++)
{
int to=v[now][i].to;
if (dis[to]>dis[now]+v[now][i].dis)
{
pre[to]=pre[now];
dis[to]=dis[now]+v[now][i].dis;
if (!vis[to]) vis[to]=,q.push(to);
}
}
}
for (int i=;i<=t1;i++)
if (ans>dis[a[i]]) ans=dis[a[i]],ans1=a[i];
printf("%ld %d %d",ans,ans1,pre[ans1]);
return ;
}
最新文章
- Ubuntu 安装php+mysql 环境
- HDU 2836 (离散化DP+区间优化)
- Java敏捷数据库迁移框架&mdash;&mdash;Flyway
- Delphi XE5教程1:语言概述
- PHP操作MySQL数据库的相关函数
- linux 网络编程:客户端与服务器通过TCP协议相互通信 + UDP
- jmeter JDBC 连接数据库
- Python:名片管理系统(增加登录功能后出现问题,求教)
- dephi FillChar 的几种写法
- windows下的vimrc
- select option 选中 取消js
- UVa Live 4725 - Airport 二分,动态规划,细节 难度: 1
- [POI2013]Polaryzacja
- redis + Tomcat 8 的session共享解决
- AspectJ入门
- uva1423 巧用拓扑排序
- c#代码加密
- Kubuntu上截屏的小技巧
- Chrome控制台的妙用之使用XPATH
- 第9项:尽量使用try-with-resources而不是try-finally(Prefer try-with-resources to try-finally)
热门文章
- [JAVA]移位运算(左移<;<;,右移>;>;和无符号右移>;>;>;)
- web 基础(二) HTML5
- Node js 入门指南(1)
- Newbe.Claptrap 框架入门,第一步 —— 创建项目,实现简易购物车
- 题解:2018级算法第三次上机 C3-Zexal的浩瀚星辰
- bugku extract 变量覆盖
- 数据可视化之powerBI基础(十九)学会使用Power BI的参数,轻松搞定动态分析
- Django框架04 /模板相关、别名/反向解析/路由分发
- 《利用Python进行数据分析》自学知识图谱-导航
- 集训作业 洛谷P1017 进制转换