PAT甲级1030.

目录

A1030

题目

样例

输入:

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出:

0 2 3 3 40

思路和坑点

　　两个优化参数的最短路径问题，而且问题的路径答案唯一，直接使用一次Dijkstra算法，同时对两个变量进行优化即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 505
#define INF 0x3fffffff
int n,m,s,d;                                //参数 
int dis[MAXN],cost[MAXN],pre[MAXN];         //最短距离数组，最小花费数组，路径前驱数组 
int G[MAXN][MAXN];                          //图 
int C[MAXN][MAXN];                          //花费 
bool vis[MAXN]={false};                     //访问标记 
void D(){                                   //两个参数的Dijkstra算法模板 
    fill(dis,dis+MAXN,INF);
    fill(cost,cost+MAXN,INF);
    dis[s]=cost[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,MIN=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&dis[j]<MIN){
                u=j;
                MIN=dis[j];
            }
        }
        if(u==-1) return;
        vis[u]=true;
        for(int v=0;v<n;v++){
            if(vis[v]==false&&G[u][v]!=INF){
                if(dis[u]+G[u][v]<dis[v]){
                    dis[v]=dis[u]+G[u][v];
                    cost[v]=cost[u]+C[u][v];
                    pre[v]=u;
                }
                else if(dis[u]+G[u][v]==dis[v]&&cost[u]+C[u][v]<cost[v]){
                    cost[v]=cost[u]+C[u][v];
                    pre[v]=u;
                }
            }
        }
    }
}
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    fill(G[0],G[0]+MAXN*MAXN,INF);                        //初始化 
    fill(C[0],C[0]+MAXN*MAXN,INF);
    fill(pre,pre+MAXN,-1);
    scanf("%d%d%d%d",&n,&m,&s,&d);                        //读入数据 
    for(int i=0;i<m;i++){                                
        int a,b,d,c;
        scanf("%d%d",&a,&b);
        scanf("%d%d",&G[a][b],&C[a][b]);
        G[b][a]=G[a][b];    C[b][a]=C[a][b];        
    } 
    D();
    vector<int> out;                                    //保存并输出路径 
    out.push_back(cost[d]);    out.push_back(dis[d]);        //最短距离和最小花费一并放入输出结果的数组中 
    while(d!=-1){
        out.push_back(d);
        d=pre[d];
    }
    for(int i=out.size()-1;i>=0;i--){
        if(i!=out.size()-1) putchar(' ');
        printf("%d",out[i]);
    }
    return 0;
}