【1030】Travel Plan (30 分)
        【摘要】 
                    #include<iostream>#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include<algorithm>  #include<map>#inclu...
    
    
    
    
  
   - 
    
     
    
    
     
      #include<iostream>
     
    
- 
    
     
    
    
     
      #include<stdio.h>
     
    
- 
    
     
    
    
     
      #include<stdlib.h>
     
    
- 
    
     
    
    
     
      #include<math.h>
     
    
- 
    
     
    
    
     
      #include<string.h>
     
    
- 
    
     
    
    
     
      #include<algorithm> 
     
    
- 
    
     
    
    
     
      #include<map>
     
    
- 
    
     
    
    
     
      #include<vector>
     
    
- 
    
     
    
    
     
      #include<queue> 
     
    
- 
    
     
    
    
     
      using namespace std;  
     
    
- 
    
     
    
    
     
      //dijkstra + DFS
     
    
- 
    
     
    
    
      
     
    
- 
    
     
    
    
     
      const int MAXV=510;  //最大顶点数
     
    
- 
    
     
    
    
     
      const int INF=0x3fffffff; //无穷大
     
    
- 
    
     
    
    
        
     
    
- 
    
     
    
    
     
      //n为顶点数,m为边数,st和ed分别为起点和终点
     
    
- 
    
     
    
    
     
      //G为距离矩阵,cost为花费矩阵
     
    
- 
    
     
    
    
     
      //d[]记录最短距离,minCost记录最短路径上的最小花费
     
    
- 
    
     
    
    
     
      int n,m,st,ed,G[MAXV][MAXV],cost[MAXV][MAXV];
     
    
- 
    
     
    
    
     
      int d[MAXV],minCost=INF;
     
    
- 
    
     
    
    
     
      bool vis[MAXV]={false}; //vis[i]==true表示顶点i已访问,初值均为false
     
    
- 
    
     
    
    
     
      vector<int> pre[MAXV];//前驱
     
    
- 
    
     
    
    
     
      vector<int> tempPath,path; //临时路径,最优路径
     
    
- 
    
     
    
    
      
     
    
- 
    
     
    
    
     
      void Dijkstra(int s){  //s为起点
     
    
- 
    
     
    
    
     	fill(d,d+MAXV,INF); //fill函数将整个d数组赋为INF
     
    
- 
    
     
    
    
     
      	d[s]=0;  //起点s到达自身的距离为0
     
    
- 
    
     
    
    
     	for(int i=0;i<n;i++){  //遍历n个顶点
     
    
- 
    
     
    
    
     		int u=-1,MIN=INF;  //u使d[u]最小,MIN存放该最小的d[u]
     
    
- 
    
     
    
    
     		for(int j=0;j<n;j++){  //找到未访问的顶点中d[]最小的
     
    
- 
    
     
    
    
     			if(vis[j] == false && d[j] <MIN){
     
    
- 
    
     
    
    
     
      				u=j;
     
    
- 
    
     
    
    
     
      				MIN=d[j];
     
    
- 
    
     
    
    
     
      			}
     
    
- 
    
     
    
    
     
      		}
     
    
- 
    
     
    
    
     		//找不到小于INF的d[u],说明剩下的顶点和起点不连通
     
    
- 
    
     
    
    
     		if(u == -1)  return ;
     
    
- 
    
     
    
    
     
      		vis[u]=true;  //标记u为已访问
     
    
- 
    
     
    
    
     		for(int v=0;v<n;v++){ 
     
    
- 
    
     
    
    
     			//如果v未访问 && u能够到达v
     
    
- 
    
     
    
    
     			if(vis[v]==false && G[u][v] !=INF){
     
    
- 
    
     
    
    
     				if(d[u]+G[u][v] < d[v]){ //以u为中介点使d[v]更小
     
    
- 
    
     
    
    
     
      					d[v]=d[u]+G[u][v]; //优化d[v]
     
    
- 
    
     
    
    
     
      					pre[v].clear(); //清空pre[v]
     
    
- 
    
     
    
    
     
      					pre[v].push_back(u); //u为v的前驱
     
    
- 
    
     
    
    
     
      				}else if(d[u]+G[u][v] == d[v]) {//找到相同长度的路径
     
    
- 
    
     
    
    
     
      					pre[v].push_back(u); //u为v的前驱之一
     
    
- 
    
     
    
    
     
      				}
     
    
- 
    
     
    
    
     
      			}
     
    
- 
    
     
    
    
     
      		}
     
    
- 
    
     
    
    
     
      	}
     
    
- 
    
     
    
    
     
      }
     
    
- 
    
     
    
    
     
      void DFS(int v){ //v为当前结点
     
    
- 
    
     
    
    
     	if(v == st){  //递归边界,到达叶子结点(路径起点)
     
    
- 
    
     
    
    
     
      		tempPath.push_back(v);
     
    
- 
    
     
    
    
     		int tempCost=0; //记录当前路径的花费之和
     
    
- 
    
     
    
    
     		for(int i=tempPath.size()-1;i>0;i--){ //倒着访问
     
    
- 
    
     
    
    
     			//当前结点id、下个结点idNext
     
    
- 
    
     
    
    
     			int id=tempPath[i] , idNext=tempPath[i-1];
     
    
- 
    
     
    
    
     
      			tempCost += cost[id][idNext]; //增加边id->idNext的边权
     
    
- 
    
     
    
    
     
      		}
     
    
- 
    
     
    
    
     		if(tempCost < minCost){  //如果当前路径的边权之和更小 
     
    
- 
    
     
    
    
     
      			minCost=tempCost;  //更新minCost
     
    
- 
    
     
    
    
     
      			path=tempPath; //更新path
     
    
- 
    
     
    
    
     
      		}
     
    
- 
    
     
    
    
     
      		tempPath.pop_back();//将刚才加入的结点删除
     
    
- 
    
     
    
    
     		return;
     
    
- 
    
     
    
    
     
      	}
     
    
- 
    
     
    
    
     
      	tempPath.push_back(v); //将当前访问结点加入临时路径tempPath最后面
     
    
- 
    
     
    
    
     	for(int i=0;i<pre[v].size();i++){
     
    
- 
    
     
    
    
     		DFS(pre[v][i]);
     
    
- 
    
     
    
    
     
      	}
     
    
- 
    
     
    
    
     
      	tempPath.pop_back();//遍历完所有前驱结点,将当前结点v删除
     
    
- 
    
     
    
    
     
      }
     
    
- 
    
     
    
    
     
      int main(){   
     
    
- 
    
     
    
    
     	scanf("%d%d%d%d",&n,&m,&st,&ed); 
     
    
- 
    
     
    
    
     	int u,v;
     
    
- 
    
     
    
    
     	fill(G[0],G[0]+MAXV*MAXV,INF);//初始化图G
     
    
- 
    
     
    
    
     	fill(cost[0],cost[0]+MAXV*MAXV,INF);
     
    
- 
    
     
    
    
     	for(int i=0; i<m; i++){
     
    
- 
    
     
    
    
     		scanf("%d%d",&u,&v); 
     
    
- 
    
     
    
    
     		scanf("%d%d",&G[u][v], &cost[u][v]);
     
    
- 
    
     
    
    
     
      		G[v][u]=G[u][v]; //因为是无向图
     
    
- 
    
     
    
    
     
      		cost[v][u]=cost[u][v]; 
     
    
- 
    
     
    
    
     
      	}
     
    
- 
    
     
    
    
     	Dijkstra(st);
     
    
- 
    
     
    
    
     	DFS(ed); //获得最优路径
     
    
- 
    
     
    
    
     	for(int i=path.size()-1; i>=0; i--){
     
    
- 
    
     
    
    
     		printf("%d ",path[i]); //倒着输出路径上的结点
     
    
- 
    
     
    
    
     
      	}
     
    
- 
    
     
    
    
     	printf("%d %d\n",d[ed],minCost);  //最短距离,最短路径上的最小花费
     
    
- 
    
     
    
    
     	system("pause"); 
     
    
- 
    
     
    
    
         return 0;   
     
    
- 
    
     
    
    
     
      }
     
    
 
文章来源: andyguo.blog.csdn.net,作者:山顶夕景,版权归原作者所有,如需转载,请联系作者。
原文链接:andyguo.blog.csdn.net/article/details/99687540
        【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
            cloudbbs@huaweicloud.com
        
        
        
        
        - 点赞
- 收藏
- 关注作者
 
             
           
评论(0)