和前几天的农场派对一样的题
把邻接矩阵换为邻接表
把朴素版Dijkstra 换成堆优化
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
const int N = 1000010, M = 2000010;
int h[N], h2[N], e[M], ne[M], w[M], idx;
int to_x[N], x_to[N], n, m;
void add(int x, int y, int z, int h[]){
e[idx] = y, ne[idx] = h[x], w[idx] = z, h[x] = idx++;
}
void wbw(int d[], int h[]){
memset(d, 0x3f, sizeof d);
d[1] = 0;
bitset<N> v;
priority_queue<pii,vector<pii> ,greater<pii>> pq;
//1号点为起点
d[1] = 0;
pq.push({0,1});
while(pq.size()){
int x = pq.top().second; pq.pop();
if(v[x]) continue;
v[x] = 1;
for(int i = h[x]; i != -1; i = ne[i]){
int y = e[i], z = w[i];
if(d[y] > d[x] + z){
d[y] = d[x] + z;
pq.push({d[y],y});
// printf("d = %d y = %d\n",d[y],y);
}
}
}
}
int main(){
int tt; cin >> tt;
while(tt--){
cin >> n >> m;
memset(h, -1, sizeof h);
memset(h2, -1, sizeof h2);
memset(x_to, 0x3f, sizeof x_to);
memset(to_x, 0x3f, sizeof to_x);
for(int i = 0; i < m; i++){
int a, b, c; cin >> a >> b >> c;
add(a, b, c, h);
add(b, a, c, h2);
}
wbw(x_to, h);//从1号点出发
wbw(to_x, h2);//反向图,到达1号点
ll ans = 0;
for(int i = 1; i <= n; i++) ans += to_x[i] + x_to[i];
cout << ans << endl;
}
return 0;
}