L2-001 紧急救援

注意题目没有说边的数量，实际最多有5e5条边，开小了第四个样例会错！！！

- 思路: Dijkstra 求最短路并且维护路径条数和最大人数。

#include<bits/stdc++.h>
using namespace std;typedef pair<int, int> pii;
typedef long long ll;
const int N = 510, M = 5e5 + 10;int n, m, s, d;
int e[M], ne[M], h[N], w[M], idx; // 链式前向星存图
int arr[N], dist[N], cnt[N], f[N], pre[N];
/*dist[i] 表示走到i这个点的最短距离cnt[i] 表示走到这个点的路径条数f[i] 表示走到这个点的最大点权和是多少pre[i] 表示是那个点走到 i 这个点 
*/
bool st[N];void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}//堆优化版
void dijkstra()
{memset(dist, 0x3f, sizeof dist);priority_queue<pii, vector<pii>, greater<pii>> heap;// 初始化heap.push({0, s});  dist[s] = 0;cnt[s] = 1, f[s] = arr[s];while(heap.size()){int u = heap.top().second;heap.pop();if(st[u]) continue;st[u] = true;for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(st[v]) continue;if(dist[v] > dist[u] + w[i]) {pre[v] = u, cnt[v] = cnt[u], f[v] = f[u] + arr[v];dist[v] = dist[u] + w[i];heap.push({dist[v], v});}else if(dist[v] == dist[u] + w[i]) {cnt[v] += cnt[u];if(f[v] < f[u] + arr[v]) {f[v] = f[u] + arr[v];pre[v] = u;}}}}
}int main()
{memset(h, -1, sizeof h);cin >> n >> m >> s >> d;for(int i = 0; i < n; i ++) cin >> arr[i];for(int i = 1; i <= m; i ++){int a, b, c;cin >> a >> b >> c;add(a, b, c), add(b, a, c);}dijkstra();cout << cnt[d] << " " << f[d] << "\n";vector<int> path;while(true) {path.push_back(d);if(d == s) break;d = pre[d];}reverse(path.begin(), path.end());for(int i = 0; i < path.size(); i ++) {if(i == path.size() - 1) cout << path[i];else cout << path[i] << " ";}return 0;
}