Day4 - L - Tram POJ - 1847
When a driver has do drive from intersection A to the intersection B he/she tries to choose the route that will minimize the number of times he/she will have to change the switches manually.
Write a program that will calculate the minimal number of switch changes necessary to travel from intersection A to intersection B.
Input
Each of the following N lines contain a sequence of integers separated by a single blank character. First number in the i-th line, Ki (0 <= Ki <= N-1), represents the number of rails going out of the i-th intersection. Next Ki numbers represents the intersections directly connected to the i-th intersection.Switch in the i-th intersection is initially pointing in the direction of the first intersection listed.
Output
Sample Input
3 2 1
2 2 3
2 3 1
2 1 2
Sample Output
0
简述:题有点难懂,给你N组数以及起点A终点B,节点标号1-N,接下来每一行第一个数表示i-th连接有几个节点,后面的第一个数是默认方向不用改变,后续的都是需要改变一次方向。
思路:看懂题意后就是一个最短路问题,默认方向权为0,改变为1,四种算法选一种即可,我这里用的是dijkstra,(其他三种在A题中有,这里就不写了),代码如下:
const int maxm = ;
const int INF = 0x7ffffff; int N, A, B, d[maxm], vis[maxm]; struct Edge {
int from, to, dist;
Edge(int _from, int _to, int _dist) : from(_from), to(_to), dist(_dist){};
}; struct Node {
int from, dist;
Node(int _from, int _dist) : from(_from), dist(_dist){}
bool operator<(const Node &a)const {
return a.dist < dist;
}
}; vector<Edge> edges;
vector<int> G[maxm]; void addedge(int u, int v, int dist) {
edges.push_back(Edge(u, v, dist));
G[u].push_back(edges.size() - );
} void init() {
for(int i = ; i <= N; ++i) {
d[i] = INF;
G[i].clear();
}
edges.clear();
memset(vis, , sizeof(vis));
} int main() {
while(scanf("%d%d%d", &N, &A, &B) != EOF) {
init();
for (int i = ; i <= N; ++i) {
int t1, t2;
scanf("%d", &t1);
for(int j = ; j < t1; ++j) {
scanf("%d", &t2);
addedge(i, t2, j == ? : );
}
}
priority_queue<Node> q;
q.push(Node(A, ));
d[A] = ;
while(!q.empty()) {
Node p = q.top();
q.pop();
if(vis[p.from])
continue;
vis[p.from] = ;
int len = G[p.from].size();
for(int i = ; i < len; ++i) {
if(d[edges[G[p.from][i]].to] > d[p.from] + edges[G[p.from][i]].dist) {
d[edges[G[p.from][i]].to] = d[p.from] + edges[G[p.from][i]].dist;
q.push(Node(edges[G[p.from][i]].to, d[edges[G[p.from][i]].to]));
}
}
}
printf("%d\n", d[B] >= INF?-:d[B]);
}
return ;
}
最新文章
- WPF整理--动态绑定到Logical Resource
- hibernate(三)基本配置,log4j、JUnit配置
- linux下的服务器搭建集成环境
- 相邻div实现一个跟着另一个自适应高度示例代码
- [课程设计]Scrum 2.0 多鱼点餐系统开发进度(第二阶段项目构思与任务规划)
- [渣译文] 使用 MVC 5 的 EF6 Code First 入门 系列:为ASP.NET MVC应用程序处理并发
- void *memmove( void* dest, const void* src, size_t count );数据拷贝,不需要CPU帮助
- xcode 执行时模拟器不可选的问题
- Node填坑教程——整理文件
- ubuntu下命令使用
- Jmeter函数组件开发
- 移动WEB 响应式设计 @media总结
- Linkin大话eclipse快捷键
- js将汉字转为相应的拼音
- 【BZOJ4569】萌萌哒(并查集,倍增)
- leetcode算法:Island Perimeter
- koa中间件
- Spark2.1.0——内置Web框架详解
- JAVA面试精选【Java基础第三部分】
- async/await 与 generator、co 的对比
热门文章
- js前台给echarts赋值
- 吴裕雄 Bootstrap 前端框架开发——Bootstrap 表格:联合使用所有表格类
- Spring boot 中发送邮件
- 本地启动tomcat的时候报java.util.concurrent.ExecutionException: java.lang.OutOfMemoryError: PermGen space
- css怎样让元素显示指定的宽高比
- 博途V13 仿真S7-300PLC 与HMI 的以太网通讯。实现简单功能 HMI 型号是TP900
- 初学微信小程序——配置问题(2)
- Duilib自定义控件
- Spark教程——(2)编写spark-submit测试Demo
- 如何在cmd中连接数据库