PAT甲级 1030 Travel Plan 单源最短路

代码如下：

//最短路径
#include<iostream>
#include<stack>
#define MAX 505
#define INF 0x3f3f3f3f
using namespace std;

int visit[MAX];//访问数组
int dis[MAX];//记录最短距离
int c[MAX];//记录每个结点的当前代价
int cost[MAX][MAX];//记录代价cost
int path[MAX];//记录路径
int mp[MAX][MAX];

int n,m;//结点数和边数
stack<int> q;//用于路径的顺序输出

void dijkstra(int s){//dijkstra
  dis[s]=0;
  c[s]=0;
  for(int i=0;i<n;i++){
    int minv=INF;
    int u=-1;
    for(int j=0;j<n;j++){
        if(dis[j]<minv&&visit[j]==0){
            minv=dis[j];
            u=j;
        }
    }
    if(u==-1){
      return;
    }
    visit[u]=1;
    for(int v=0;v<n;v++){
        if(visit[v]==0&&mp[u][v]!=INF){
            if(dis[v]>dis[u]+mp[u][v]){
                dis[v]=dis[u]+mp[u][v];
                c[v]=c[u]+cost[u][v];
                path[v]=u;//path[v]的值等于它的前一个结点的编号
            }else if(dis[v]==dis[u]+mp[u][v]){
                if(c[v]>c[u]+cost[u][v]){
                    c[v]=c[u]+cost[u][v];
                    path[v]=u;
                }
            }
        }
    }
  }
}

int main(){
  for(int i=0;i<MAX;i++){
    visit[i]=0;
    path[i]=-1;
    dis[i]=INF;
    c[i]=INF;
  }
  for(int i=0;i<MAX;i++){
    for(int j=0;j<MAX;j++){
        mp[i][j]=INF;
    }
  }
  int start,goal;
  cin>>n>>m>>start>>goal;
  int a,b,len,co;
  for(int i=0;i<m;i++){
    cin>>a>>b>>len>>co;
    mp[a][b]=mp[b][a]=len;
    cost[a][b]=cost[b][a]=co;
  }
  dijkstra(start);
  int p=goal;
  while(path[p]!=-1){//将最短路径上的结点入栈
    q.push(p);
    p=path[p];
  }
  cout<<start<<' ';
  while(!q.empty()){//结点依次出栈
    cout<<q.top()<<' ';
    q.pop();
  }
  cout<<dis[goal]<<' '<<c[goal];
  return 0;
}