这个代码在提交OJ时提示输出超限,求大神们解决

Arice徐新凯 发布于 2014/06/16 09:19
阅读 1K+
收藏 0

题目描述

由n个点和m条无向边构成的无向连通图,每条边都有长度d和花费p,给你起点s终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
请用Dijkstra算法或Floyd算法等求解!

输入

输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数 s,t; 起点s,终点t。
(2<=n<=2000, n-1<=m<=(n*(n-1))/2, 1<=d<=10000, 1<=p<=10000, s != t)

输出

输出:一行有两个数, 最短距离及其花费。

样例输入

3 2
1 2 5 6
2 3 4 5
1 3 

样例输出

9 11 

提示

本题是一个求最短路径的题目。可以用Dijkstra算法或Floyd算法等。

下面是我的代码:

#include<stdio.h>
#include<memory.h>
#define MAX 1000000000
int a[2005][2005][2],len[2005],quan[2005];
int main()
{
	int n,m,i,j,w,x,y,z,count,min;
	while(scanf("%d%d",&n,&m),n!=0||m!=0){
		for(i=0;i<=n;i++)
			for(j=0;j<=n;j++){
				a[i][j][0]=a[i][j][1]=MAX;
			}
			memset(len,0,replace(len));
			memset(quan,0,replace(quan));
			for(i=0;i<m;i++){
				scanf("%d%d%d%d",&w,&x,&y,&z);
				if(a[w][x][0]>y){
					a[w][x][0]=y;
					a[w][x][1]=z;
					a[x][w][0]=y;
					a[x][w][1]=z;
				}
			}
			scanf("%d%d",&x,&y);
			while(1){
				min=0;
				for(i=1;i<=n;i++){
					if(a[x][i][0]<a[x][min][0]){
						min=i;
					}
					else if(a[x][i][0]==a[x][min][0]){
						if(a[x][i][1]<a[x][min][1]) min=i;
					}
				}
				len[min]=a[x][min][0];
				quan[min]=a[x][min][1];
				if(min==y) break;
				for(i=1;i<=n;i++){
					if(x==i)continue;
					if(a[min][i][0]<MAX&&a[x][i][0]>a[x][min][0]+a[min][i][0])
					{
						a[x][i][0]=a[x][min][0]+a[min][i][0];
						a[x][i][1]=a[x][min][1]+a[min][i][1];
					}
					else if(a[min][i][0]<MAX&&a[x][i][0]==a[x][min][0]+a[min][i][0]){
						if(a[min][i][1]<MAX&&a[x][i][1]>a[x][min][1]+a[min][i][1]){
							a[x][i][0]=a[x][min][0]+a[min][i][0];
							a[x][i][1]=a[x][min][1]+a[min][i][1];
						}
					}
				}
				a[x][min][0]=a[x][min][1]=MAX;
			}
			printf("%d %d\n",len[y],quan[y]);
	}
	return 0;
}
int replace(char str[])
{
	int i=0;
	int n=0;
	while(str[i++])
		if(str[i-1]==' ')
		{
			str[i-1]='-';
			n++;
		}
		return n;
}


加载中
返回顶部
顶部