hdu 题目4034 （floyd算法的理解变形）

深碍√TFBOYSˉ_ 2022-09-18 07:50 157阅读 0赞

[http://acm.hdu.edu.cn/showproblem.php?pid=4034][http_acm.hdu.edu.cn_showproblem.php_pid_4034]

/***************************
    # 2013-11-11 21:24:17 
    # Time: 46MS   Memory: 280K
    # Author: zyh
    ***************************/ 
    #define N 105
    #include<stdio.h>
    
    int a[N][N];
     
    int main()
    {
    	int tt,t,n,i,j,k,m;
    	scanf("%d",&t);
    	for(tt=1;tt<=t;tt++){
    		m=0;
    		scanf("%d",&n);
    		for(i=1;i<=n;i++){
    			for(j=1;j<=n;j++){
    				scanf("%d",&a[i][j]);
    				if(a[i][j]) m++;
    			}
    		}
    		//floyd算法 
    		int flag=1,count=0;  
    	    for(i=1;i<=n;i++)  
    	        for(j=1;j<=n;j++)  
    	        {  
    	            if( i==j )continue;  
    	            for(k=1;k<=n;k++)  
    	            {  
    	                if(i==k||j==k || !a[i][k] || !a[k][j])continue;  
    	                if(a[i][j]>a[i][k]+a[k][j]) //如果给出的不是i，j之间的最短路径 ，直接退出 
    	                { flag = 0;  goto ans; }  //利用goto跳出多重循环 
    	                else  if(a[i][j]==a[i][k]+a[k][j])  //有其他路径可以到达，则去掉当前路径 
    	                {  
    	                    m--;  
    	                    break;  
    	                }  
    	            }  
    	        }  
    		ans:
    			printf("Case %d: ",tt);
    			if(!flag) puts("impossible");
    			else	printf("%d\n",m);
    	}
    	return 0; 
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_4034]: http://acm.hdu.edu.cn/showproblem.php?pid=4034

发表评论取消回复

表情：

评论列表（有 0 条评论，157人围观）

还没有评论，来说两句吧...

相关阅读

相关 Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦

雨点打透心脏的1/2处/ 2023年07月17日 15:59/ 0 赞/ 144 阅读

相关 Floyd算法

Floyd算法的理解 Floyd算法是用来求两点之间的最短路径的，它的一大特点就是三循环，时间复杂度是n^3。对于Floyd算法，相信初学者大多都会有一个疑问，就是

迷南。/ 2023年07月08日 09:18/ 0 赞/ 39 阅读

相关 hdu 题目4034 （floyd算法的理解变形）

[http://acm.hdu.edu.cn/showproblem.php?pid=4034][http_acm.hdu.edu.cn_showproblem.php_pid

深碍√TFBOYSˉ_/ 2022年09月18日 07:50/ 0 赞/ 158 阅读

相关算法题目——电梯(HDU-1008)

题目链接：[HDU-1008][] ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q

柔情只为你懂/ 2022年09月10日 15:25/ 0 赞/ 197 阅读

相关 HDU 4034 Graph

Problem Description Everyone knows how to calculate the shortest path in a directed gra

系统管理员/ 2022年08月09日 13:46/ 0 赞/ 27 阅读

相关 POJ 2253 Frogger floyd变形

滴，集训第二十五天打卡。最近又好热好热了呀... POJ 2253 Frogger Freddy Frog is sitting on a stone in the m

曾经终败给现在/ 2022年06月10日 05:55/ 0 赞/ 171 阅读

相关 hdoj 1181 变形课（floyd）

变形课 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

àì夳堔傛蜴生んèń/ 2022年04月10日 05:54/ 0 赞/ 194 阅读

相关 hdu1181(变形课)

[ ][Link 1] [ ][Link 1] include"iostream" using namespace std; char s[100]; char S

向右看齐/ 2021年12月22日 09:57/ 0 赞/ 263 阅读

相关 Emergency（变形弗洛伊德 Floyd）

题目： Emergency 题目描述 Kudo’s real name is not Kudo. Her name is Kudryavka Anatol

绝地灬酷狼/ 2021年09月26日 16:34/ 0 赞/ 381 阅读

相关 floyd算法

floyd算法是通过动态规划特别是记住公式，f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = m

喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 437 阅读