1012The Best Rank

↩ ↪

July 08, 2020 AlgorithmC++skill

Question

现已知n个考生的3门分数，平均分可以按照这三门算出来。然后分别对这四个分数从高到低排序，这样对每个考生来说有4个排名。k个查询，对于每一个学生id，输出当前id学生的最好的排名和它对应的分数，如果名次相同，按照A>C>M>E的顺序输出～如果当前id不存在，输出N/A。

Sample Input

5 6
310101 98 85 88
310102 70 95 88
310103 82 87 94
310104 91 91 91
310105 85 90 90
310101
310102
310103
310104
310105
999999

Sample Output

1 C
1 M
1 E
1 A
3 A
N/A

这道题其实也没什么好说的，比较常规的一道题，但不知道为什么给分那么高，写这篇博客只是为了提醒我自己，C++构造数组的时候可以使用变量来做数组的大小参数，但是一定要在定义数组之前，确定变量的数值。不然虽然自己运行的时候可以运行，但是提交到算法测试平台上的时候会引起段错误。

今天用了两个小时都在找为什么触发段错误了。太傻了这个错误TvT

AC代码:

//date:2020.02.10
//author:ViViWilliam
//issue3
#include<iostream>
using namespace std;
int main(){
	//城市数,道路数,所在地,目的地
	int N,M,c1,c2;
	cin>>N>>M>>c1>>c2;
	int team[N]={0};
	int road[N][N];
	int length[N]={0};
	int teamsum[N]={0};
	int min[N]={0},sum;
	sum=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			road[i][j]=10000;
		}
	}
	for(int i=0;i<N;i++){
		cin>>team[i];
	}

	for(int i=0;i<M;i++){
		int x,y;
		cin>>x;
		cin>>y;
		cin>>road[x][y];
		road[y][x] = road[x][y];
	}

	for(int i=0;i<N;i++){
		length[i]=road[c1][i];
		if(road[c1][i]!=10000){
		teamsum[i] = team[i]+team[c1];
			min[i]=1;
		}

	}
	length[c1]=0;
	min[c1]=1;
	teamsum[c1] = team[c1];

	int last,lastnum;
	int i;
	int h[N]={0};
	h[c1]=1;
	int a=0;


	while(1){

		int minid=10000,minro=10000;
		//找到一个起始点
		for(int d=0;d<N;d++){
			if (h[d]==0){
				minid=d;
				minro=length[d];
				break;
			}
		}
		//所有点都遍历完
		if(minid==10000)
		break;
		//找出最小值,作为起点
		for(int m=0;m<N;m++){
			if(h[m]==0&&length[m]<minro){
				minid = m;
				minro = length[m];
			}
		}
		h[minid]=1;
		i = minid;
			if(i == c1){
				continue;
			}
			//依次排查
			for(int j=0;j<N;j++){
				if(h[j] == 0 && road[i][j] != 10000){

				if(j==c1)
					continue;
				//如果当前位置的长度加上此位置到某点的位置小于等于
				if((length[i]+road[i][j])<=length[j]){

					//如果小于,总的 					
						if((length[i]+road[i][j])<length[j]){
							teamsum[j] = teamsum[i]+team[j];
							length[j] = length[i]+road[i][j];
							min[j] = min[i];
						}
						else if(length[i]+road[i][j]==length[j]){
							min[j]+=min[i];
							if(teamsum[j]<(teamsum[i]+team[j])){
							teamsum[j]=teamsum[i]+team[j];
						}


				}
		    }
		    }
			}


	}
	cout<<min[c2]<<" "<<teamsum[c2];
return 0;
}