题目链接: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 ;
}

最新文章

  1. hadoop在网页客户端的maven配置
  2. 【手把手教你全文检索】Lucene索引的【增、删、改、查】
  3. 2015-2-10 Linux 知识
  4. Rotate String
  5. 【CSS3】Advanced9:Transformation
  6. [Javascript] Drawing Styles on HTML5 Canvas
  7. salt-API基本验证命令
  8. 測试之路2——对照XML文件1
  9. linux 下日常使用便利工具
  10. Spring知识点回顾(03)Bean的 Scope
  11. codevs 1006 等差数列
  12. HTTP2概述
  13. JPA 连表查询
  14. python中filter、map、reduce的区别
  15. YUV介绍
  16. 关于四种语言中substring()方法参数值的解析
  17. 理解maven命令package、install、deploy的联系与区别
  18. PostgreSQL 的命令行工具 psql 的常用命令
  19. Object C函数指针@selector
  20. static final 内部类

热门文章

  1. ElasticSearch中Date
  2. 16.1112 模拟考试 T1
  3. 【Git】Git 本地的撤销修改和删除操作
  4. Linux系统下rz/sz工具的安装
  5. 使用Sharesdk实现第三方平台登录(qq,新浪微博)
  6. go--常量&amp;运算符
  7. 多语言业务错误日志收集监控工具Sentry 安装与使用
  8. http状态码的分类
  9. 4.JAVA语言基础部分&mdash;枚举与泛型
  10. C#使用PrintDocument打印 多页 打印预览