[SPOJ 30669] Ada and Trip
2024-08-26 21:16:02
[题目链接]
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 ; }
最新文章
- linux下使用yum安装mysql
- Type-Length-Value编码
- Android 动画特效
- 配置Tomcat数据源
- Python网络编码
- 【转】掌握java枚举类型(enum type)
- Redis同步(主从复制)
- Java Tomcat 中调用.net DLL的方法
- OSG调试信息显示
- Net 并行知识学习
- 分享自己使用CSS的public
- Vulkan Tutorial 20 Vertex buffer creation
- Python Cookbook(第3版)中文版:15.15 C字符串转换为Python字符串
- 6个项目带你全面掌握Laravel框架
- 【XSY2484】mex 离散化 线段树
- windows2008r2系统破解登录密码方法
- 安装ansible集群管理和配置密钥互信
- Effective Java Methods Common to All Objects
- Suricata在ubuntu14.04环境下安装
- 「SCOI2011」糖果