7-4 Ambulance Dispatch (30分) 浙江大学2019年考研复试上机题

 #include<cstdio>

    
 #include<vector>
    
 #include<algorithm>
    
 #include<string>
    
 using namespace std;
    
 const int maxn = 1050;
    
 const int inf = 1000000000;
    
 int Ns,Na,K,M;
    
 int weight[maxn];
    
 int G[maxn][maxn];
    
 int S[maxn][maxn];//边权为1，解决街道问题 
    
 int d[maxn][maxn];//记录最短时间用,要初始化 
    
 int street[maxn][maxn];//记录最短距离，要初始化 
    
 bool vis[maxn]={false};//要初始化 
    
 int pre[maxn][maxn];// pre[s][v]，当源点为s时v的前驱结点 ,无需初始化 
    
 void Dijkstra(int s)
    
 {
    
 	fill(d[s],d[s]+maxn,inf);
    
 	fill(street[s],street[s]+maxn,inf);
    
 	d[s][s]=street[s][s]=0;
    
 	pre[s][s] = -1;
    
 	while(1){
    
 		int u=-1, min=inf;
    
 		for(int j=1; j<=Ns+Na; j++){
    
 			if(vis[j]==false&&d[s][j]<min){
    
 				u = j;
    
 				min = d[s][j];
    
 			}
    
 		}
    
 		if(u==-1) return;
    
 		vis[u]=true;
    
 		for(int v=1; v<=Ns+Na; v++){
    
 			if(vis[v]==false&&G[u][v]!=inf){
    
 				if(d[s][u]+G[u][v]<d[s][v]){
    
 					d[s][v] = d[s][u]+G[u][v];
    
 					street[s][v] = street[s][u]+S[u][v];
    
 					pre[s][v] = u;
    
 				}
    
 				else if(d[s][u]+G[u][v]==d[s][v]&&street[s][u]+S[u][v]<=street[s][v]){//这里是小于等于 
    
 					street[s][v] = street[s][u]+S[u][v];
    
 					pre[s][v] = u;
    
 				}
    
 			}
    
 		}
    
 	}
    
 }
    
  
    
 int main()
    
 {
    
 	fill(G[0],G[0]+maxn*maxn,inf);
    
 	fill(S[0],S[0]+maxn*maxn,inf);
    
 	scanf("%d%d",&Ns,&Na);
    
 	for(int i=Ns+1; i<=Ns+Na; i++){
    
 		scanf("%d",&weight[i]); 
    
 	}
    
 	scanf("%d",&M);
    
 	for(int i=0; i<M; i++){
    
 		char str[10];
    
 		int u,v;
    
 		scanf("%s",str);
    
 		if(str[0]=='A'){
    
 			sscanf(str, "A-%d", &u);
    
 			u+=Ns;
    
 		}
    
 		else u = stoi(str);
    
 		scanf("%s",str);
    
 		if(str[0]=='A'){
    
 			sscanf(str, "A-%d", &v);
    
 			v+=Ns;
    
 		}
    
 		else v = stoi(str);
    
 		scanf("%d",&G[u][v]);
    
 		G[v][u] = G[u][v]; 
    
 		S[u][v] = S[v][u] = 1;
    
 	}
    
 	for(int i=Ns+1; i<=Ns+Na; i++){
    
 		Dijkstra(i);
    
 		fill(vis,vis+maxn,false);
    
 	}
    
 	scanf("%d",&K);
    
 	int s;
    
 	for(int i=0; i<K; i++){
    
 		scanf("%d",&s);
    
 		int minTime=inf, maxAmbu=-1, minStreets=inf, index=-1;
    
 		for(int j=Ns+1; j<=Ns+Na; j++){
    
 			if(weight[j]>0){
    
 				if(d[j][s]<minTime){
    
 					index = j;
    
 					minTime = d[j][s];
    
 					maxAmbu = weight[j];
    
 					minStreets = street[j][s];
    
 				}
    
 				else if(d[j][s]==minTime&&weight[j]>maxAmbu){
    
 					index = j;
    
 					maxAmbu = weight[j];
    
 					minStreets = street[j][s];
    
 				}
    
 				else if(d[j][s]==minTime&&weight[j]==maxAmbu&&
    
 				street[j][s]<minStreets){
    
 					index = j;
    
 					minStreets = street[j][s];
    
 				}
    
 			}
    
 		}
    
 		if(index==-1) printf("All Busy\n");
    
 		else{
    
 			weight[index]--;
    
 			vector<int> v;
    
 			while(s!=-1){
    
 				v.push_back(s);
    
 				s = pre[index][s];
    
 			}
    
 			printf("A-%d",v[v.size()-1]-Ns);
    
 			for(int z=v.size()-2; z>=0; z--){
    
 				if(v[z]>Ns) printf(" A-%d",v[z]-Ns);//有可能输出时碰到救护中心 
    
 				else printf(" %d",v[z]);
    
 			}
    
 			printf("\n");
    
 			printf("%d\n",minTime);
    
 		}
    
 	}
    
 	return 0;
    
 } 
    
  
    
  
    
  
    
    
    
    
    AI写代码