L2-001 紧急救援 (25 分)

传送门

一些代码能力太差，不过去年不会写的题今年能A了还是很开心的，就是写的好烦啊

idea：魔改dijkstra，对于最短路数量在得出最短路距离之后再更新，详见文末样例，之前被这组卡了

code

#include 

using namespace std;

typedef long long ll;

typedef pair pii;

const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll N = 510;

pii dist[N];
ll cnt[N], pa[N];
ll n, m;

struct node {
    ll to, len;
};

vector g[N];
ll a[N];

struct note {
    ll u, dis, person;

    bool operator<(const note &b) const {
        if (dis != b.dis) return dis < b.dis;
        return person > b.person;
    }
};

void dijkstra(ll s) {
    for (ll i = 0; i < n; ++i) {
        dist[i] = {inf, 0};
    }

    priority_queue > que;
    dist[s] = {0, a[s]};
    que.push({s, 0, a[s]});
//    cnt[s] = 1;

    while (!que.empty()) {
        auto tmp = que.top();
        que.pop();
        ll from = tmp.u;
        ll person = tmp.person;
        ll dis = tmp.dis;

        if (dis > dist[from].first ||
            (dis == dist[from].first && person < dist[from].second)) {
            continue;
        }

        for (auto tt : g[from]) {
            ll to = tt.to;
            ll len = tt.len;
            if (dist[to].first > dist[from].first + len) {
                dist[to].first = dist[from].first + len;
                dist[to].second = dist[from].second + a[to];
//                cnt[to] = cnt[from];
                pa[to] = from;
                que.push({to, dist[to].first, dist[to].second});
            } else if (dist[to].first == dist[from].first + len) {
//                cnt[to] += cnt[from];
                if (dist[from].second + a[to] > dist[to].second) {
                    dist[to].second = dist[from].second + a[to];
                    pa[to] = from;
                    que.push({to, dist[to].first, dist[to].second});
                }
            }
        }

    }
}


signed main() {
    ll s, d;
    cin >> n >> m >> s >> d;
    for (ll i = 0; i < n; ++i) cin >> a[i];
    for (ll i = 1; i <= m; ++i) {
        ll x, y, len;
        cin >> x >> y >> len;
        if (x == y) continue;
        g[x].push_back({y, len});
        g[y].push_back({x, len});
    }

    dijkstra(s);

    cnt[s] = 1;
    vector > sov;
    for (int i = 0; i < n; ++i) {
        sov.push_back({i, dist[i].first});
    }
    sort(sov.begin(), sov.end(), [&](auto x, auto y) { return x.second < y.second; });

    for (auto tmp : sov) {
        int u = tmp.first;
        for (auto tt : g[u]) {
            int to = tt.to;
            int len = tt.len;
            if (dist[to].first == dist[u].first + len) {
                cnt[to] += cnt[u];
            }
        }
    }

    cout << cnt[d] << " " << dist[d].second << endl;

    vector res;
    ll nw = d;
    while (nw != s) {
        res.push_back(nw);
        nw = pa[nw];
    }
    res.push_back(s);
    reverse(res.begin(), res.end());
    ll siz = res.size();
    for (ll i = 0; i < siz; ++i) cout << res[i] << (i == siz - 1 ? "" : " ");

}

测试样例：

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