PTA 7-10（图） 旅游规划（25 分） 25分代码

最短路问题

更新最短路径的时候考虑最小花费

（注：博客作为交流使用，切勿抄袭应付作业）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 500+7, INF = 0x7f7f7f7f;

int n, m, fir, en;
int u, v, l, h, cnt;
int head[maxn], d[maxn], d1[maxn], vis[maxn];
struct edge {
    int u, l, h;
    int next;
}e[2*maxn*maxn];

void init() {
    scanf("%d %d %d %d", &n, &m, &fir, &en);
    cnt = 0;
    memset(head, -1, sizeof head);
    for(int i = 0; i < m; ++i) {
        scanf("%d %d %d %d", &u, &v, &l, &h);
        e[cnt].u = v; e[cnt].l = l; e[cnt].h = h; e[cnt].next = head[u]; head[u] = cnt++;
        e[cnt].u = u; e[cnt].l = l; e[cnt].h = h; e[cnt].next = head[v]; head[v] = cnt++;
    }
}

void solve() {
    memset(d, INF, sizeof d);
    memset(d1, INF, sizeof d1);
    memset(vis, 0, sizeof vis);

    for(int i = head[fir]; i != -1; i = e[i].next) {
        d[e[i].u] = e[i].l; d1[e[i].u] = e[i].h;
    }
    int ans = 0, ans1 = 0;
    while(1) {
        int t = -1;
        for(int i = 0; i < n; ++i) {
            if(!vis[i] && (t == -1 || (d[t] > d[i] || (d[t] == d[i] && d1[t] < d1[i])) )) t = i;
        }
        if(t == -1) break;
        //ans += d[t]; ans1 += d1[t];
        vis[t] = 1;
        for(int i = head[t]; i != -1; i = e[i].next) {
            if(d[e[i].u] > d[t]+e[i].l) {
                d[e[i].u] = d[t] + e[i].l;
                d1[e[i].u] = d1[t] + e[i].h;
            }
            else if(d[e[i].u] == d[t]+e[i].l) {
                d1[e[i].u] = min(d1[e[i].u], d1[t] + e[i].h);
            }
        }
    }
    cout << d[en] << " " << d1[en] << endl;
}

int main() {
    init();
    solve();
    return 0;
}
/*
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
*/