[题目链接]

https://www.spoj.com/problems/ADATRIP/

[算法]

直接使用dijkstra堆优化算法即可

[代码]

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + ;
const int INF = 2e9; struct edge
{
int to,w,nxt;
} e[MAXN << ]; int i,j,tot,a,b,l,n,m,u,q;
int head[MAXN];
pair<int,int> ans; inline void addedge(int u,int v,int w)
{
tot++;
e[tot] = (edge){v,w,head[u]};
head[u] = tot;
}
inline pair<int,int> dijkstra(int s)
{
int i,l,r,cur,ans1,ans2,v,w;
static int dist[MAXN];
static bool visited[MAXN];
priority_queue< pair<int,int> > q;
for (i = ; i < n; i++)
{
dist[i] = INF;
visited[i] = false;
}
q.push(make_pair(,s));
dist[s] = ;
while (!q.empty())
{
cur = q.top().second;
q.pop();
if (visited[cur]) continue;
visited[cur] = true;
for (i = head[cur]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (dist[cur] + w < dist[v])
{
dist[v] = dist[cur] + w;
q.push(make_pair(-dist[v],v));
}
}
}
ans1 = ;
for (i = ; i < n; i++)
{
if (dist[i] != INF)
ans1 = max(ans1,dist[i]);
}
ans2 = ;
for (i = ; i < n; i++)
{
if (dist[i] == ans1)
ans2++;
}
return make_pair(ans1,ans2);
} int main()
{ scanf("%d%d%d",&n,&m,&q);
for (i = ; i <= m; i++)
{
scanf("%d%d%d",&a,&b,&l);
if (l == ) continue;
addedge(a,b,l);
addedge(b,a,l);
}
while (q--)
{
scanf("%d",&u);
ans = dijkstra(u);
printf("%d %d\n",ans.first,ans.second);
} return ; }

最新文章

  1. linux下使用yum安装mysql
  2. Type-Length-Value编码
  3. Android 动画特效
  4. 配置Tomcat数据源
  5. Python网络编码
  6. 【转】掌握java枚举类型(enum type)
  7. Redis同步(主从复制)
  8. Java Tomcat 中调用.net DLL的方法
  9. OSG调试信息显示
  10. Net 并行知识学习
  11. 分享自己使用CSS的public
  12. Vulkan Tutorial 20 Vertex buffer creation
  13. Python Cookbook(第3版)中文版:15.15 C字符串转换为Python字符串
  14. 6个项目带你全面掌握Laravel框架
  15. 【XSY2484】mex 离散化 线段树
  16. windows2008r2系统破解登录密码方法
  17. 安装ansible集群管理和配置密钥互信
  18. Effective Java Methods Common to All Objects
  19. Suricata在ubuntu14.04环境下安装
  20. 「SCOI2011」糖果

热门文章

  1. 安卓手机USB无法共享、上网或卡顿的解决方法
  2. WCF分佈式事務支持
  3. mysql 统计按天、星期、按月数据的各种 sql 语句 (转录)
  4. Cache-Control官方文档
  5. Robot Framework(六)变量
  6. Xilinx 7系列FPGA部分重配置【2】
  7. sql server安装出现的一点小问题
  8. eas之获得任何一个KDTable的选中行
  9. 一键安装LNMP(适合centos7)
  10. shell脚本编程及bash特性