L3-007 天梯地图

拿起题就开始写，最后提交测试点2和测试点3就是过不去。
感觉一点问题都没有，好郁闷，找了半天，发现地点的编号是0开始的，而我一直在从1遍历....
思路就是两个dijkstra，这两次思路是完全一样的，只是一个是最短距离最少节点，一个是最短时间最短距离，所以分别需要增加一个累计经过节点数量和累计节点距离（cnt和distances）。
结果我都是用dist来存的，第一个dist表示的是最短路径，第二个表示的是最短时间。

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int dist[510],visited[510];
int edges[510][510],hao[510][510]; 
int pre[510];//前一个节点 
int cnt[510];//累计节点数量 
int distances[510];//累计节点距离 
int minTime,minPath;
void dijkstra(int dist[],int visited[],int n,int s){//最短节点最少 
     dist[s]=0;
	 for(int i=0;i<n;i++){
	 	int minv=inf,minx;
	 	for(int j=1;j<=n;j++){
	 		if(!visited[j]&&dist[j]<minv){
	 			minv=dist[j];
	 			minx=j;
			 }
		}
		visited[minx]=1;
		for(int j=0;j<n;j++){//更新 
			if(minv+edges[minx][j]<dist[j]){//更短 
				dist[j]=minv+edges[minx][j];
				pre[j]=minx;
				cnt[j]=cnt[minx]+1;
			}else if(minv+edges[minx][j]==dist[j]){//是否更新 
				if(cnt[minx]+1<cnt[j]){
					pre[j]=minx;
					cnt[j]=cnt[minx]+1;
				}
			}
		}
	 }	
}
void dijkstra2(int dist[],int visited[],int n,int s){//最快路径最短 
     dist[s]=0;
	 for(int i=0;i<n;i++){
	 	int minv=inf,minx;
	 	for(int j=1;j<=n;j++){
	 		if(!visited[j]&&dist[j]<minv){
	 			minv=dist[j];
	 			minx=j;
			 }
		}
		visited[minx]=1;//已经来过 
		for(int j=0;j<n;j++){//更新 
			if(minv+hao[minx][j]<dist[j]){//更快 
				dist[j]=minv+hao[minx][j];
				pre[j]=minx;
				distances[j]=distances[minx]+edges[minx][j];
			}else if(minv+hao[minx][j]==dist[j]){//是否更新 
				if(distances[minx]+edges[minx][j]<distances[j]){
					pre[j]=minx;
					distances[j]=distances[minx]+edges[minx][j];
				}
			}
		}
	 }	
}
int main(){
	memset(dist,0x3f,sizeof(dist));
	memset(edges,0x3f,sizeof(edges));
	memset(visited,0,sizeof(visited));
	memset(pre,-1,sizeof(pre));
	memset(hao,0x3f,sizeof(hao));
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,way,dist,shi;
		cin>>a>>b>>way>>dist>>shi;
		if(way){
			edges[a][b]=dist;
			hao[a][b]=shi;
		}else{
			edges[a][b]=edges[b][a]=dist;
			hao[a][b]=hao[b][a]=shi;
		}
	}
	int start,ed;
	cin>>start>>ed;
	dijkstra(dist,visited,n,start);
    minPath=dist[ed];//最短距离 
	vector<int> vec,vec2;
	set<vector<int>> st;
	int tmp = ed;
	vec.push_back(tmp);
	while(pre[tmp]!=-1){
		vec.push_back(pre[tmp]);
		tmp=pre[tmp];
	}
    st.insert(vec);
	memset(visited,0,sizeof(visited));
    memset(pre,-1,sizeof(pre));
    memset(dist,0x3f,sizeof(dist));
    dijkstra2(dist,visited,n,start);
    minTime=dist[ed];//最快 
    tmp=ed;
    vec2.push_back(tmp);
	while(pre[tmp]!=-1){
		vec2.push_back(pre[tmp]);
		tmp=pre[tmp];
	}
    st.insert(vec2);
    if(st.size()==1){
    	cout<<"Time = "<<minTime<<"; Distance = "<<minPath<<": ";
	    int flag = 0;
		for(int i=vec.size()-1;i>=0;i--){
			if(flag) cout << " => ";
			cout << vec[i];
			flag++;
		}
	}else{
		cout<<"Time = "<<minTime<<": ";
		int flag = 0;
		for(int i=vec2.size()-1;i>=0;i--){
			if(flag) cout << " => ";
			cout << vec2[i];
			flag++;
		}
		cout<<"\nDistance = "<<minPath<<": ";
		flag = 0;
		for(int i=vec.size()-1;i>=0;i--){
			if(flag) cout << " => ";
			cout << vec[i];
			flag++;
		}
	}
	return 0;
}