题解 | 最短路径问题

#include <cmath>
#include <endian.h>
#include <iostream>
#include <vector>
using namespace std;

typedef struct Edge{
    int position;
    int cost;
    int distance;
}Edge;

vector<Edge> ascs[1001];
int cost[1001];// 最小花费
int dist[1001];// 最小距离
bool mask[1001];// 是否访问标记
const int Max = 1215752192;// 最大值

Edge getMin(){
    Edge min;
    min.position = Max;
    min.cost = Max;
    min.distance = Max;
    for(int i=1; i<=dist[0]; i++){
        if(mask[i]) continue;
        if(min.distance > dist[i] || (min.distance == dist[i] && min.cost > cost[i])){
            min.position = i;
            min.cost = cost[i];
            min.distance = dist[i];
        }
    }
    return min;
}

void dijkstra(int s){
    // 处理起点
    Edge min;
    min.position = s;
    cost[min.position] = 0;
    dist[min.position] = 0;
    mask[min.position] = true;
    // 循环处理每个点
    for(int i=0; i<dist[0]; i++){
        for(Edge t : ascs[min.position]){
            // 跳过已经标记的
            if(mask[t.position]) continue;
            // 更新最小距离，最小花费
            if(dist[t.position] ==  Max || 
            dist[t.position] > dist[min.position] + t.distance ||
            (dist[t.position] == dist[min.position] + t.distance && cost[t.position] > cost [min.position] + t.cost)){
                dist[t.position] = dist[min.position] + t.distance;
                cost[t.position] = cost [min.position] + t.cost;
            }
        }
        // 寻找最小值
        min = getMin();
        if(min.position == Max) break;
        mask[min.position] = true;
    }
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        if(n==0 && m==0)
            break;
        // 初始化
        for(int i=1; i<=n; i++){
            cost[i] = Max;
            dist[i] = Max;
            mask[i] = false;
            ascs[i].clear();
        }
        dist[0] = n;   
        // 读取数据构造图
        int tmp, t;
        for(int i=0; i<m; i++){
            // tmp -> e->position
            cin >> tmp;
            Edge *e = new Edge;
            cin >> e->position >> e->distance >> e->cost;
            ascs[tmp].push_back(*e);
            // e->position -> tmp
            t=tmp;
            tmp = e->position;
            e->position = t;
            ascs[tmp].push_back(*e);
        }
        // 计算最短距离，以及花费
        int s;
        cin >> s >> t;
        dijkstra(s);
        cout << dist[t] << " " << cost[t] << endl;
    }
}