【1030】Travel Plan (30 分)

#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;   
}