题目链接:http://poj.org/problem?id=1847

题意:给了N个交叉口,每个交叉口有自己能转到的交叉口。

注意这里:First number in the i-th line, Ki (0 <= Ki <= N-1), represents the number of rails going out of the i-th intersection.

即每一行的第二个数字代表该交叉口默认的通向,是不需要手动转的,剩下的交叉口想去的话都需要手动转一次。

现在想要从A口走到B口,走的路程想要转的次数时最少的,问最少转的值。

建图求最短路即可

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
#include <string>
typedef long long LL;
#define INF 0x3f3f3f3f
#define met(a, b) memset(a, b, sizeof(a))
#define N 515 using namespace std; int G[N][N], n; void Floyd()
{
for(int k=; k<=n; k++)
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
G[i][j] = min(G[i][j], G[i][k]+G[k][j]);
}
} int main()
{
int a, b, num, k;
while(scanf("%d %d %d", &n, &a, &b) != EOF)
{
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
G[i][j] = INF;
G[i][i] = ;
} for(int i=; i<=n; i++)
{
scanf("%d", &k);
for(int j=; j<=k; j++)
{
scanf("%d", &num);
if(j == ) G[i][num] = ;
else G[i][num] = ;
}
}
Floyd();
if(G[a][b] == INF)puts("-1");
else printf("%d\n", G[a][b]);
}
return ;
}

最新文章

  1. iscroll 下拉刷新功能
  2. flex上下固定中间滚动布局
  3. [转]svn常用命令
  4. Shell之date用法
  5. eclipse折叠快捷键
  6. 使用Jconsole监控weblogic的配置方法
  7. LTE 切换过程中的数据切换
  8. python函数 位置参数,关键字参数,可变参数优先级
  9. chrome 浏览器 开发者工具 性能检测 参数解释
  10. 转:一个C语言实现的类似协程库(StateThreads)
  11. AVA取整以及四舍五入
  12. 批量扫描互联网无线路由设备telnet,并获取WIFI密码
  13. OC &amp; java 对比
  14. ionic 图片轮播问题
  15. WinExec函数,启动其他应用程序
  16. Redis Cluster的搭建与部署,实现redis的分布式方案
  17. 机器学习算法与Python实践之(五)k均值聚类(k-means)
  18. 添加 [DataContract] 到 Entity Framework 6.0 POCO Template
  19. 5 -- Hibernate的基本用法 --4 深入Hibernate配置文件
  20. iconv用法解读

热门文章

  1. Linux Mint 没有 language support 语言支持解决方案
  2. 【POJ】1556 The Doors(计算几何基础+spfa)
  3. 原来还有这样的记词方法_Java版记不规则动词_博主推荐
  4. 运行时(iOS)
  5. Spring3.1 Cache注解
  6. SQL Server访问MySql
  7. 相关css 细节处理 neat.css
  8. .NET开发问题汇总
  9. 拦截webview调用系统浏览器打开链接
  10. PHP获取某远程网站的服务器时间