1. 全栈程序员必看首页

hdu 3631 Shortest Path（Floyd）[通俗易懂]

全栈程序员-站长 • • 未分类 • 阅读 32

hdu 3631 Shortest Path（Floyd）

大家好，又见面了，我是全栈君。

题目链接：Shortest Path

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3962    Accepted Submission(s): 938

Problem Description
When YY was a boy and LMY was a girl, they trained for NOI (National Olympiad in Informatics) in GD team. One day, GD team’s coach, Prof. GUO asked them to solve the following shortest-path problem.

There is a weighted directed multigraph G. And there are following two operations for the weighted directed multigraph:

(1) Mark a vertex in the graph.

(2) Find the shortest-path between two vertices only through marked vertices.

For it was the first time that LMY faced such a problem, she was very nervous. At this moment, YY decided to help LMY to analyze the shortest-path problem. With the help of YY, LMY solved the problem at once, admiring YY very much. Since then, when LMY meets problems, she always calls YY to analyze the problems for her. Of course, YY is very glad to help LMY. Finally, it is known to us all, YY and LMY become programming lovers.

Could you also solve the shortest-path problem?

 
Input
The input consists of multiple test cases. For each test case, the first line contains three integers N, M and Q, where N is the number of vertices in the given graph, N≤300; M is the number of arcs, M≤100000; and Q is the number of operations, Q ≤100000. All vertices are number as 0, 1, 2, … , N – 1, respectively. Initially all vertices are unmarked. Each of the next M lines describes an arc by three integers (x, y, c): initial vertex (x), terminal vertex (y), and the weight of the arc (c). (c > 0) Then each of the next Q lines describes an operation, where operation “0 x” represents that vertex x is marked, and operation “1 x y” finds the length of shortest-path between x and y only through marked vertices. There is a blank line between two consecutive test cases.

End of input is indicated by a line containing N = M = Q = 0.

 
Output
Start each test case with “Case #:” on a single line, where # is the case number starting from 1.

For operation “0 x”, if vertex x has been marked, output “ERROR! At point x”.

For operation “1 x y”, if vertex x or vertex y isn’t marked, output “ERROR! At path x to y”; if y isn’t reachable from x through marked vertices, output “No such path”; otherwise output the length of the shortest-path. The format is showed as sample output.

There is a blank line between two consecutive test cases.

 
Sample Input 
   
   

    
    5 10 10
1 2 6335
0 4 5725
3 3 6963
4 0 8146
1 2 9962
1 0 1943
2 1 2392
4 2 154
2 2 7422
1 3 9896
0 1
0 3
0 2
0 4
0 4
0 1
1 3 3
1 1 1
0 3
0 4
0 0 0

 
Sample Output 
   
   

    
    Case 1:
ERROR! At point 4
ERROR! At point 1
0
0
ERROR! At point 3
ERROR! At point 4

 
Source
2010 Asia Regional Tianjin Site —— Online Contest 


代码例如以下：

#include <cstdio>
#include <cstring>
#define INF 0x3fffffff  
#define MAXN 317
int dis[MAXN][MAXN];
int mark[MAXN];
int n;
int min(int a, int b)
{
	return a < b ? a:b;
}
void init()
{
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(i == j)
				dis[i][j] = 0;
			else
				dis[i][j] = INF;
		}
	}
}

void Floyd(int k)
{
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
		}
	}
}

int main()
{
	int i, j;
	int M, Q;
	int a, b, w;
	int cas = 0;
	while(~scanf("%d%d%d",&n,&M,&Q))
	{
		if(n == 0 && M == 0 && Q == 0)
			break;
		if(cas != 0)
			printf("\n");
		init();
		memset(mark,0,sizeof(mark));
		for(i =  0; i < M; i++)
		{
			scanf("%d%d%d",&a,&b,&w);
			if(w < dis[a][b])
			{
				dis[a][b] = w;
			}
		}
		int op, x, y;
		printf("Case %d:\n",++cas);
		for(i = 0; i < Q; i++)
		{
			scanf("%d",&op);
			if(op == 0)
			{
				scanf("%d",&x);
				if(mark[x])
				{
					printf("ERROR! At point %d\n",x);
					continue;
				}
				mark[x] = 1;
				Floyd(x);
			}
			else if(op == 1)
			{
				scanf("%d%d",&x,&y);
				if(!mark[x] || !mark[y])
				{
					printf("ERROR! At path %d to %d\n",x,y);
					continue;
				}
				if(dis[x][y] >= INF)
					printf("No such path\n");
				else
					printf("%d\n",dis[x][y]);
			}
		}
	}
	return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115664.html原文链接：https://javaforall.net

赞 (0)
全栈程序员-站长的头像全栈程序员-站长
0 0


相关推荐

  • 怎么创建CSV文件和怎么打开CSV文件[通俗易懂]

    怎么创建CSV文件和怎么打开CSV文件[通俗易懂]

    怎么创建CSV文件和怎么打开CSV文件[通俗易懂]CSV（CommaSeparatedValues逗号分隔值）。.csv是一种文件格式（如.txt、.doc等），也可理解.csv文件就是一种特殊格式的纯文本文件。即是一组字符序列，字符之间已英文字符的逗号或制表符（Tab）分隔。在windows系统环境上.csv文件打开方式有多种，如记事本、excel、Notepad++等，只要是文本编辑器都能正确打开。1.工具/原料E…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月20日
  • 郁闷中…………

    郁闷中…………

    郁闷中…………

    全栈程序员-站长的头像 全栈程序员-站长
    2021年8月5日
  • 二进制和十进制的转换机制是什么?_转化成二进制

    二进制和十进制的转换机制是什么?_转化成二进制

    二进制和十进制的转换机制是什么?_转化成二进制一、十进制转换成二进制1.1正整数转二进制要点：除二取余，倒序排列，高位补零。方法：将正的十进制数除以二，得到的商再除以二，依次类推直至商为0或1时为止，然后在旁边标出各步的余数，最后倒着写出来，高位补零。注：计算机内部表示数的字节单位是定长的，如8位，16位，或32位。所以，位数不够时，高位补零。1.2负整数转二进制方法：先将对应的正整数转换成二进制后，对二进制取…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年10月18日
  • 计算机等级二级java试题(计算机二级考试题库)

    计算机等级二级java试题(计算机二级考试题库)

    第一章数据结构与算法【考点1】算法的基本概念1、算法：是指一组有穷的指令集，是解题方案的准确而完整的描述。算法不等于程序，也不等于计算方法。2、算法的基本特征：1）确定性，算法中每一步骤都必须有明确定义，不允许有多义性；2）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止；3）可行性，算法原则上能够精确地执行；4）拥有足够的情报。3、算法的组成…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年4月10日
  • 基于Redis实现DelayQueue延迟队列设计方案(附源码)「建议收藏」

    基于Redis实现DelayQueue延迟队列设计方案(附源码)「建议收藏」

    基于Redis实现DelayQueue延迟队列设计方案(附源码)「建议收藏」应用场景创建订单10分钟之后自动支付叫预约单专车出行前30分钟发送短信提示订单超时取消…等等…实现方式最简单的方式,定时扫表;例如每分钟扫表一次十分钟之后未支付的订单进行主动支付;优点:简单缺点:每分钟全局扫表,浪费资源,有一分钟延迟使用RabbitMq实现RabbitMq实现延迟队列优点:开源,现成的稳定的实现方案;缺点:RabbitMq是一个…

    全栈程序员-站长的头像 全栈程序员-站长
    2022年5月3日
  • C# StreamReader/StreamWriter与FileStream用法详解

    C# StreamReader/StreamWriter与FileStream用法详解

    C# StreamReader/StreamWriter与FileStream用法详解一、StreamReader类共有10个构造函数StreamReader(Stream)   // 为指定的流初始化StreamReader类的新实例。FileStreamfs=newFileStream(@”D:\Readme.txt”,FileMode.Open);StreamReadersr=newStreamRea

    全栈程序员-站长的头像 全栈程序员-站长
    2022年7月23日

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号