题目描述

为了提高服务器的耐受能力,很多流量大的网站都会架设多台服务器,而互联网的路由能找到线路最短的一台服务器。 现在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 ;
}

最新文章

  1. Ubuntu 安装php+mysql 环境
  2. HDU 2836 (离散化DP+区间优化)
  3. Java敏捷数据库迁移框架&mdash;&mdash;Flyway
  4. Delphi XE5教程1:语言概述
  5. PHP操作MySQL数据库的相关函数
  6. linux 网络编程:客户端与服务器通过TCP协议相互通信 + UDP
  7. jmeter JDBC 连接数据库
  8. Python:名片管理系统(增加登录功能后出现问题,求教)
  9. dephi FillChar 的几种写法
  10. windows下的vimrc
  11. select option 选中 取消js
  12. UVa Live 4725 - Airport 二分,动态规划,细节 难度: 1
  13. [POI2013]Polaryzacja
  14. redis + Tomcat 8 的session共享解决
  15. AspectJ入门
  16. uva1423 巧用拓扑排序
  17. c#代码加密
  18. Kubuntu上截屏的小技巧
  19. Chrome控制台的妙用之使用XPATH
  20. 第9项:尽量使用try-with-resources而不是try-finally(Prefer try-with-resources to try-finally)

热门文章

  1. [JAVA]移位运算(左移&lt;&lt;,右移&gt;&gt;和无符号右移&gt;&gt;&gt;)
  2. web 基础(二) HTML5
  3. Node js 入门指南(1)
  4. Newbe.Claptrap 框架入门,第一步 —— 创建项目,实现简易购物车
  5. 题解:2018级算法第三次上机 C3-Zexal的浩瀚星辰
  6. bugku extract 变量覆盖
  7. 数据可视化之powerBI基础(十九)学会使用Power BI的参数,轻松搞定动态分析
  8. Django框架04 /模板相关、别名/反向解析/路由分发
  9. 《利用Python进行数据分析》自学知识图谱-导航
  10. 集训作业 洛谷P1017 进制转换