思路：
正权最短路，全图一去一回，Dijkstra。稀疏图要用邻接表，邻接表的反向建图方法：用三个数组（u[maxn]、v[maxn]、w[maxn]）记录每一条路，然后重新录入。邻接矩阵的反向建图方法：矩阵转置（详见：Previous_BLOG）。
注意：
数组开精确了，RE一次。使用 int，疯狂WA。
代码：
WA（int）：
#include <iostream>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std
;
const int maxn
= 1000005;
int T
,N
,M
;
int U
[maxn
],V
[maxn
],W
[maxn
];
int dis
[maxn
];
int vis
[maxn
];
struct NODE
{
int id
;
int dis
;
NODE(int id
,int dis
) : id(id
) , dis(dis
) {} ;
friend bool operator
> (NODE a
,NODE b
)
{
return a
.dis
> b
.dis
;
}
};
priority_queue
<NODE
, vector
<NODE
> , greater
<NODE
> > Q
;
struct EDGE
{
int to
;
int w
;
int fo
;
};
EDGE E
[maxn
];
int tail
[maxn
];
void ADDEDGE(int i
,int u
,int v
,int w
){
E
[i
].to
= v
;
E
[i
].w
= w
;
E
[i
].fo
= tail
[u
];
tail
[u
] = i
;
return ;
}
void INIT(){
memset(dis
,INF
,sizeof(dis
));
memset(vis
,0,sizeof(vis
));
memset(tail
,-1,sizeof(tail
));
return ;
}
int IJK(){
Q
.push(NODE(1,0));dis
[1]=0;
int sum
=0;
while(Q
.size()){
NODE cur
= Q
.top() ; Q
.pop();
if(vis
[cur
.id
])
continue;
vis
[cur
.id
] = true
;
sum
+= dis
[cur
.id
];
for(int i
=tail
[cur
.id
] ; ~i
; i
= E
[i
].fo
){
EDGE path
= E
[i
];
if(vis
[path
.to
])
continue;
if(dis
[path
.to
] > dis
[cur
.id
] + path
.w
){
dis
[path
.to
] = dis
[cur
.id
] + path
.w
;
Q
.push(NODE(path
.to
, dis
[path
.to
]));
}
}
}
return sum
;
}
int main(){
ios
::sync_with_stdio(false
);
cin
.tie(0);
cin
>>T
;
while(T
--){
cin
>>N
>>M
;
for(int i
=1;i
<=M
;i
++)
cin
>>U
[i
]>>V
[i
]>>W
[i
];
INIT();
for(int i
=1;i
<=M
;i
++)
ADDEDGE(i
, U
[i
] , V
[i
] , W
[i
]);
int t1
= IJK();
INIT();
for(int i
=1;i
<=M
;i
++)
ADDEDGE(i
, V
[i
] , U
[i
] , W
[i
]);
int t2
= IJK();
cout
<<t1
+t2
<<endl
;
}
return 0;
}
long long：7735ms 32980kB
#include <iostream>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std
;
const int maxn
= 1000005;
int T
,N
,M
;
int U
[maxn
],V
[maxn
],W
[maxn
];
int dis
[maxn
];
bool vis
[maxn
];
struct NODE
{
int id
;
int dis
;
NODE(int id
,int dis
) : id(id
) , dis(dis
) {} ;
friend bool operator
> (NODE a
,NODE b
)
{
return a
.dis
> b
.dis
;
}
};
priority_queue
<NODE
, vector
<NODE
> , greater
<NODE
> > Q
;
struct EDGE
{
int to
;
int w
;
int fo
;
};
EDGE E
[maxn
];
int tail
[maxn
];
void ADDEDGE(int i
,int u
,int v
,int w
){
E
[i
].to
= v
;
E
[i
].w
= w
;
E
[i
].fo
= tail
[u
];
tail
[u
] = i
;
return ;
}
void INIT(){
memset(dis
,INF
,sizeof(dis
));
memset(vis
,0,sizeof(vis
));
memset(tail
,-1,sizeof(tail
));
return ;
}
long long IJK(){
Q
.push(NODE(1,0));dis
[1]=0;
long long sum
=0;
while(Q
.size()){
NODE cur
= Q
.top() ; Q
.pop();
if(vis
[cur
.id
])
continue;
vis
[cur
.id
] = true
;
sum
+= dis
[cur
.id
];
for(int i
=tail
[cur
.id
] ; ~i
; i
= E
[i
].fo
){
EDGE path
= E
[i
];
if(vis
[path
.to
])
continue;
if(dis
[path
.to
] > dis
[cur
.id
] + path
.w
){
dis
[path
.to
] = dis
[cur
.id
] + path
.w
;
Q
.push(NODE(path
.to
, dis
[path
.to
]));
}
}
}
return sum
;
}
int main(){
ios
::sync_with_stdio(false
);
cin
.tie(0);
cin
>>T
;
while(T
--){
cin
>>N
>>M
;
for(int i
=1;i
<=M
;i
++)
cin
>>U
[i
]>>V
[i
]>>W
[i
];
INIT();
for(int i
=1;i
<=M
;i
++)
ADDEDGE(i
, U
[i
] , V
[i
] , W
[i
]);
long long t1
= IJK();
INIT();
for(int i
=1;i
<=M
;i
++)
ADDEDGE(i
, V
[i
] , U
[i
] , W
[i
]);
long long t2
= IJK();
long long ans
= t1
+ t2
;
cout
<<ans
<<endl
;
}
return 0;
}
