L2-001 紧急救援

L2-001 紧急救援

L2-001 紧急救援 - 团体程序设计天梯赛-练习集

用堆优化的dijskstra，

#include <bits/stdc++.h>

using namespace std;
const int N = 505;
class Dist{
public:
    int u;
    int d;
    Dist(int u_, int d_):u(u_),d(d_){}
    bool operator <(const Dist& other)const{
        return d > other.d;// 小顶堆
    }
};
int pre[N];// 记录当前城市的上一个城市
int s;// 起点
void print(int x){// 输出路径
    if(x == s) {
        cout << s;
        return;
    }
    print(pre[x]);
    cout << " " << x;
}
void solve() {
    int n, m, d; // s为起点 d为终点
    cin >> n >> m >> s >> d;
    int a[n + 1], w[n + 1];//a为每个城市的救援队数  w为能到达某城市的救援队数
    vector<bool> vis(n + 1, false);
    vector<Dist> g[n + 1];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int num[n + 1];// 记录到达某座城市最短路径条数
    w[s] = a[s];
    num[s] = 1;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back(Dist(v, w));
        g[v].push_back(Dist(u, w));
    }

    priority_queue<Dist> q;
    vector<int> dis(n + 1, INT_MAX);
    dis[s] = 0;
    q.push(Dist(s, 0));
    while (!q.empty()) {
        Dist cur = q.top();
        q.pop();
        int u = cur.u;
        if (vis[u]) continue;
        vis[u] = true;
        for(auto& e : g[u]){
            int v = e.u, d = e.d;
            if(dis[v] > dis[u] + d){
                dis[v] = dis[u] + d;
                num[v] = num[u];
                pre[v] = u;
                w[v] = w[u] + a[v];
                q.push(Dist(v, dis[v]));
            }else if(dis[v] == dis[u] + d){
                if(w[u] + a[v] > w[v]){
                    w[v] = w[u] + a[v];
                    pre[v] = u;
                }
                num[v] += num[u];
            }
        }

    }
    cout << num[d] << " " << w[d] << endl;
    print(d);

}


int main() {
#ifdef ACM_LOCAL
    freopen("data.in", "r", stdin);
//    freopen("data.out", "w", stdout);
#endif
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}