题解 | 最短路径问题

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n,m;
struct PII{
    int d; //距离
    int p; //花费
    PII(int d,int p):d(d),p(p){}
    PII():d(0),p(0){}  //无参数构造函数，默认初始化d和p为0；
    //定义有参构造函数后，必须再手动定义一个无参构造函数，用于声明全局结构体数组时给系统使用；
};

const int N = 1010;
PII g[N][N],dist[N];
bool s[N];

void Dijkstra(int start,int end){
    
    dist[start].d=0;
    dist[start].p=0;

    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){  
            if(!s[j] && (t==-1 || dist[j].d<dist[t].d)){  //t==-1 别写成赋值t=-1
                t=j;
            }
        }

        s[t]=true;

        for(int j=1;j<=n;j++){
            if(!s[j] && g[t][j].d!=0x3f3f3f3f){
                if(dist[t].d+g[t][j].d<dist[j].d){ 
                    //如果从t到j的距离更短，则更新距离和花费，哪怕花费更高也更新
                    dist[j].d=dist[t].d+g[t][j].d;
                    dist[j].p=dist[t].p+g[t][j].p;
                }else if(dist[t].d+g[t][j].d==dist[j].d){
                    //如果两距离一样，则选花费低的
                    dist[j].p=min(dist[j].p,dist[t].p+g[t][j].p);
                }       
            }
        }
    }

    if(dist[end].d==0x3f3f3f3f)printf("-1");
    else printf("%d %d",dist[end].d,dist[end].p);

}

PII mymin(PII a,PII b){
    if(a.d<b.d){
        return a;
    }else if(a.d>b.d){
        return b;
    }
    
    return a.p<b.p?a:b;
}

int main() {
    while (scanf("%d%d",&n,&m)!=EOF) {  //scanf("%d%d",&n,&m)!=EOF 避免死循环
        if(m==0 && n==0){
            break;
        }

        //重置PII g[N][N]h和dist[N]数组 以及标记数组s
        for(int i = 1;i<=n;i++){
            dist[i]=PII();
            s[i]=false;
        }
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=n;j++){
                g[i][j]=PII();
            }
        }


        while(m--){
            int a,b,d,p;
            scanf("%d%d%d%d",&a,&b,&d,&p);
            // 处理重边，保留更优的边
            g[a][b] = mymin(PII(d, p),g[a][b]);
            g[b][a] = mymin(PII(d, p),g[b][a]);;  // 无向图
        }
        int s,t;
        scanf("%d%d",&s,&t);

        Dijkstra(s, t);
    }
}
// 64 位输出请用 printf("%lld")

【关键点】：

1. 每次换下一组测试用例时，记得重置 g[N][N]、dist[N] 以及标记数组s[N];
2. 因为这是无向图，也就是说当题目输入a->b,b->a 两条距离和花费不一样的边时，选择一个最优的就行；因此要处理重边：
3. 在Dijkstra算法中根据节点t更新其他节点时：距离的优先级要大于花费，在距离相同的情况下，才选花费少的；否则优先选距离短的；