九度OJ 1162:I Wanna Go Home(我想回家) (最短路径)

2024-04-02 02:18

本文主要是介绍九度OJ 1162:I Wanna Go Home(我想回家) (最短路径),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:870

解决:415

题目描述:

    The country is facing a terrible civil war----cities in the country are divided into two parts supporting different leaders. As a merchant, Mr. M does not pay attention to politics but he actually knows the severe situation, and your task is to help him reach home as soon as possible. 
    "For the sake of safety,", said Mr.M, "your route should contain at most 1 road which connects two cities of different camp."
    Would you please tell Mr. M at least how long will it take to reach his sweet home?

输入:

    The input contains multiple test cases.
    The first line of each case is an integer N (2<=N<=600), representing the number of cities in the country.
    The second line contains one integer M (0<=M<=10000), which is the number of roads.
    The following M lines are the information of the roads. Each line contains three integers A, B and T, which means the road between city A and city B will cost time T. T is in the range of [1,500].
    Next part contains N integers, which are either 1 or 2. The i-th integer shows the supporting leader of city i. 
    To simplify the problem, we assume that Mr. M starts from city 1 and his target is city 2. City 1 always supports leader 1 while city 2 is at the same side of leader 2. 
    Note that all roads are bidirectional and there is at most 1 road between two cities.
Input is ended with a case of N=0.

输出:

    For each test case, output one integer representing the minimum time to reach home.
    If it is impossible to reach home according to Mr. M's demands, output -1 instead.

样例输入:
2
1
1 2 100
1 2
3
3
1 2 100
1 3 40
2 3 50
1 2 1
5
5
3 1 200
5 3 150
2 5 160
4 3 170
4 2 170
1 2 2 2 1
0
样例输出:
100
90
540
来源:
2011年北京大学计算机研究生机试真题

思路:

题目大意是N个城市分属于两个敌对集团,要从城市1到城市2(分别属于两个集团),只能有一条路跨集团,求最短路径。

我的思路是,求城市1到其集团中其它城市的最短路径,城市2也同样,然后对集团间存在的路径i到j,求d(1,i)+d(i,j)+d(j,2)的最小值。


代码:

#include <stdio.h>#define N 600
#define M 10000
#define INF 1e8int n;
int D[N][N];
int support[N], visit[2][N], dis[2][N];void init()
{for (int i=0; i<n; i++){support[i] = 0;visit[0][i] = visit[1][i] = 0;dis[0][i] = dis[1][i] = INF;for (int j=0; j<n; j++){D[i][j] = INF;}}
}void printdis(int s)
{int i;for (i=0; i<n; i++){if (support[i] == s)printf("%d\n", dis[s][i]);}printf("\n");
}void dijkstra(int s)
{int i, j;for (i=0; i<n; i++){if (support[i] == s)dis[s][i] = D[s][i];}dis[s][s] = 0;visit[s][s] = 1;//printdis(s);int mind;int k;for (i=0; i<n; i++){mind = INF;for (j=0; j<n; j++){if ( support[j] == s && !visit[s][j] && (dis[s][j]<mind) ){mind = dis[s][j];k = j;}}if (mind == INF)break;visit[s][k] = 1;for (j=0; j<n; j++){if ( support[j] == s && !visit[s][j] && (dis[s][k]+D[k][j] < dis[s][j]) ){dis[s][j] = dis[s][k]+D[k][j];}}}//printdis(s);
}int Min(int a, int b)
{return (a<b) ? a : b;
}int main(void)
{int m, i, j;int a, b, d;int min;while (scanf("%d", &n) != EOF && n){init();scanf("%d", &m);for(i=0; i<m; i++){scanf("%d%d%d", &a, &b, &d);D[a-1][b-1] = D[b-1][a-1] = d;}for(i=0; i<n; i++){   scanf("%d", &a);support[i] = a-1;}       dijkstra(0);dijkstra(1);min = INF;for (i=0; i<n; i++){for (j=0; j<n; j++){if (support[i] == 0 && support[j] == 1){min = Min(dis[0][i] + D[i][j] + dis[1][j], min);}}}if (min == INF)printf("-1\n");elseprintf("%d\n", min);}return 0;
}
/**************************************************************Problem: 1162User: liangrx06Language: CResult: AcceptedTime:20 msMemory:2336 kb
****************************************************************/


这篇关于九度OJ 1162:I Wanna Go Home(我想回家) (最短路径)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/868717

相关文章

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法:临时设置(Windows用`set`,Linux/macOS用`export`)、永久设置(系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量(适用于当前会话)永久设置环境变量(Windows系统

go动态限制并发数量的实现示例

《go动态限制并发数量的实现示例》本文主要介绍了Go并发控制方法,通过带缓冲通道和第三方库实现并发数量限制,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录带有缓冲大小的通道使用第三方库其他控制并发的方法因为go从语言层面支持并发,所以面试百分百会问到

Go语言并发之通知退出机制的实现

《Go语言并发之通知退出机制的实现》本文主要介绍了Go语言并发之通知退出机制的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录1、通知退出机制1.1 进程/main函数退出1.2 通过channel退出1.3 通过cont

Go语言编译环境设置教程

《Go语言编译环境设置教程》Go语言支持高并发(goroutine)、自动垃圾回收,编译为跨平台二进制文件,云原生兼容且社区活跃,开发便捷,内置测试与vet工具辅助检测错误,依赖模块化管理,提升开发效... 目录Go语言优势下载 Go  配置编译环境配置 GOPROXYIDE 设置(VS Code)一些基本

使用Go实现文件复制的完整流程

《使用Go实现文件复制的完整流程》本案例将实现一个实用的文件操作工具:将一个文件的内容完整复制到另一个文件中,这是文件处理中的常见任务,比如配置文件备份、日志迁移、用户上传文件转存等,文中通过代码示例... 目录案例说明涉及China编程知识点示例代码代码解析示例运行练习扩展小结案例说明我们将通过标准库 os

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs

深入理解Go语言中二维切片的使用

《深入理解Go语言中二维切片的使用》本文深入讲解了Go语言中二维切片的概念与应用,用于表示矩阵、表格等二维数据结构,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习吧... 目录引言二维切片的基本概念定义创建二维切片二维切片的操作访问元素修改元素遍历二维切片二维切片的动态调整追加行动态

go中的时间处理过程

《go中的时间处理过程》:本文主要介绍go中的时间处理过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 获取当前时间2 获取当前时间戳3 获取当前时间的字符串格式4 相互转化4.1 时间戳转时间字符串 (int64 > string)4.2 时间字符串转时间

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的