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