hdu 2680 Choose the best route 解题报告
2024-08-30 14:31:31
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2680
题目意思:实质就是给定一个多源点到单一终点的最短路。
卑鄙题~~~有向图。初始化map时 千万不要写成 map[i][j] = map[j][i] = X。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; #define INF 0xfffffff
const int maxn = + ;
int dist[maxn], map[maxn][maxn], vis[maxn];
int n, m, s; void Init()
{
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
map[i][j] = (i == j ? : INF);
}
int p, q, t, w;
for (int i = ; i < m; i++)
{
scanf("%d%d%d", &p, &q, &t);
if (map[p][q] > t)
map[p][q] = t; // 写成map[p][q] = map[q][p] = t 会wa的!!!
}
scanf("%d", &w);
for (int i = ; i < w; i++)
{
scanf("%d", &p);
map[][p] = map[p][] = ;
}
for (int i = ; i <= n; i++)
dist[i] = map[][i];
} void Dijkstra()
{
int u, maxx;
memset(vis, , sizeof(vis));
for (int i = ; i <= n; i++)
{
maxx = INF;
for (int j = ; j <= n; j++)
{
if (!vis[j] && dist[j] < maxx)
maxx = dist[u=j];
}
vis[u] = ;
for (int j = ; j <= n; j++)
{
if (dist[j] > dist[u] + map[u][j])
dist[j] = dist[u] + map[u][j];
}
}
} int main()
{
while (scanf("%d%d%d", &n, &m, &s) != EOF)
{
Init();
Dijkstra();
printf("%d\n", dist[s] == INF ? - : dist[s]);
}
return ;
}
最新文章
- hadoop在网页客户端的maven配置
- 【手把手教你全文检索】Lucene索引的【增、删、改、查】
- 2015-2-10 Linux 知识
- Rotate String
- 【CSS3】Advanced9:Transformation
- [Javascript] Drawing Styles on HTML5 Canvas
- salt-API基本验证命令
- 測试之路2——对照XML文件1
- linux 下日常使用便利工具
- Spring知识点回顾(03)Bean的 Scope
- codevs 1006 等差数列
- HTTP2概述
- JPA 连表查询
- python中filter、map、reduce的区别
- YUV介绍
- 关于四种语言中substring()方法参数值的解析
- 理解maven命令package、install、deploy的联系与区别
- PostgreSQL 的命令行工具 psql 的常用命令
- Object C函数指针@selector
- static final 内部类