游客 注册 | 登录
中文 | En

1088 - 最爱的城市

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

一天小明捧着一本世界地图在看，突然小明拿起笔，将他最爱的那些城市标记出来，并且随机的将这些城市中的某些用线段两两连接起来。
小明量出了每条线段的长度，现在小明想知道在这些线段组成的图中任意两个城市之间的最短距离是多少。

题目输入

输入包含多组测试数据。
每组输入第一行为两个正整数n（n<=10）和m（m<=n*(n-1)/2），n表示城市个数，m表示线段个数。
接下来m行，每行输入三个整数a，b和l，表示a市与b市之间存在一条线段，线段长度为l。（a与b不同）
每组最后一行输入两个整数x和y，表示问题：x市与y市之间的最短距离是多少。（x与y不同）
城市标号为1~n，l<=20。

题目输出

对于每组输入，输出x市与y市之间的最短距离，如果x市与y市之间非连通，则输出“No path”。

输入/输出样例

输入格式

4 4
1 2 4
1 3 1
1 4 1
2 3 1
2 4

输出格式

3

C语言解答

#include<stdio.h>
#include<string.h>

const int inf=1000000000;

int n,g[10][10];

void floyd()
{
	int i,j,k;
	for(k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(g[i][k]+g[k][j]<g[i][j])
					g[i][j]=g[i][k]+g[k][j];
}

int main()
{
	int m,a,b,l,i,j;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				g[i][j]=inf;
		while(m--)
		{
			scanf("%d%d%d",&a,&b,&l);
			g[a-1][b-1]=g[b-1][a-1]=l;
		}
		floyd();
		scanf("%d%d",&a,&b);
		if(g[a-1][b-1]==inf)
			puts("No path");
		else
			printf("%d\n",g[a-1][b-1]);
	}
	return 0;
}

C++解答

#include<stdio.h>
#include<string.h>

const int inf=1000000000;

int n,g[10][10];

void floyd()
{
	int i,j,k;
	for(k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(g[i][k]+g[k][j]<g[i][j])
					g[i][j]=g[i][k]+g[k][j];
}

int main()
{
	int m,a,b,l,i,j;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				g[i][j]=inf;
		while(m--)
		{
			scanf("%d%d%d",&a,&b,&l);
			g[a-1][b-1]=g[b-1][a-1]=l;
		}
		floyd();
		scanf("%d%d",&a,&b);
		if(g[a-1][b-1]==inf)
			puts("No path");
		else
			printf("%d\n",g[a-1][b-1]);
	}
	return 0;
}

Java解答

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int m,n,a,b,l,x,y,k,i,j;
		int[] [] diat=null;
		while(in.hasNext()) {
			n = in.nextInt();
			m = in.nextInt();
			diat = new int[n][n];
			for(i=0;i<n;i++) {
				for(j=0;j<n;j++) {
					diat[i][j]=100;
				}
			}
			for(int h=0;h<m;h++) {
				a=in.nextInt();
				b=in.nextInt();
				l=in.nextInt();
				diat[a-1][b-1]=l;
				diat[b-1][a-1]=l;		
			}
			for(k=0;k<n;k++) {
				for(i=0;i<n;i++) {
					for(j=0;j<n;j++) {
					if(diat[i][j]>(diat[i][k]+diat[k][j])){
						diat[i][j]=diat[i][k]+diat[k][j];
					}
				}
			}	
		}
			x=in.nextInt()-1;
			y=in.nextInt()-1;
			if(diat[x][y]!=100)
				System.out.println(diat[x][y]);
			else
				System.out.println("No path");
	}

}
}
请先登陆