昨天的题太水了，堆优化跑的不爽，今天换了一个题，1000000个点，1000000条边= =
试一试邻接表
写的过程中遇到了一些问题，由于习惯于把数据结构封装在 struct 里，结果 int [1000000] 导致 struct 爆栈，此问题亟待解决..
实力碾压SPFA 2500 ms，有图为证
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXP (1000000 + 10)
#define MAXQ MAXP
#define INF 2000000000
using namespace std; struct Edge{
int u, v, w;
}e[MAXQ]; //struct Graph{
static int firstEdge[MAXP], cnt;
struct E{
int v, w, next;
E(){}
E(int U, int V, int W):v(V),w(W),next(firstEdge[U]){}
}edges[MAXQ];
inline void reset(){
memset(firstEdge, -1, sizeof(firstEdge));
cnt = 0;
}
inline void addEdge(int u, int v, int w){
edges[cnt] = E(u, v, w);
firstEdge[u] = cnt++;
}
//}g; int d1[MAXP], d2[MAXP], *d; template <class T>
T min(T &a, T &b){
return a < b ? a : b;
} //struct BHeap{
int heap[MAXP], n, index[MAXP];
//BHeap(){}
inline void up(int i){
for (int j = i >> 1; j > 0; j >>= 1){
if (d[heap[i]] < d[heap[j]]){
swap(index[heap[i]], index[heap[j]]);
swap(heap[i], heap[j]);
i = j;
}
else break;
}
}
inline void down(int i){
for (int j = i << 1; j <= n; j <<= 1){
j += (j < n) && (d[heap[j]] > d[heap[j + 1]]);
if (d[heap[i]] > d[heap[j]]){
swap(index[heap[i]], index[heap[j]]);
swap(heap[i], heap[j]);
i = j;
}
else break;
}
}
inline void push(int i){
heap[++n] = i;
index[i] = n;
up(n);
}
inline int pop(){
if (!n) return 0;
swap(index[heap[1]], index[heap[n]]);
swap(heap[1], heap[n--]);
down(1);
return heap[n + 1];
}
void BHeap(int N){
n = 0;
for (int i = 2; i <= N; i++){
push(i);
}
}
//}heap; bool been[MAXP]; void Dijkstra(){
memset(been, 0, sizeof(been));
been[1] = 1;
while (int v = pop()){
been[v] = 1;
for (int i = firstEdge[v]; ~i; i = edges[i].next){
if (!been[edges[i].v]){
if (d[edges[i].v] > d[v] + edges[i].w){
d[edges[i].v] = d[v] + edges[i].w;
up(index[edges[i].v]);
}
}
}
}
} int main(){
int n, p, q;
freopen("fin.c", "r", stdin);
scanf("%d", &n);
while (n--){
scanf("%d%d", &p, &q);
for (int i = 0; i < q; i++){
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
}
reset();
d = d1;
for (int i = 1; i <= p; i++){
d[i] = INF;
}
for (int i = 0; i < q; i++){
addEdge(e[i].u, e[i].v, e[i].w);
if (e[i].u == 1){
d[e[i].v] = min(d[e[i].v], e[i].w);
}
}
BHeap(p);
Dijkstra(); reset();
d = d2;
for (int i = 1; i <= p; i++){
d[i] = INF;
}
for (int i = 0; i < q; i++){
addEdge(e[i].v, e[i].u, e[i].w);
if (e[i].v == 1){
d[e[i].u] = min(d[e[i].u], e[i].w);
}
}
BHeap(p);
Dijkstra(); long long ans = 0;
for (int i = 2; i <= p; i++){
ans += d1[i] + d2[i];
}
printf("%lld\n", ans);
}
}