题目链接：https://vjudge.net/contest/123674#problem/D
题意：一张个向图，求从点1开始到其他各点的最短路权值和加上从其他各点到点1的最短路权值和 首先注意的是这是一个有向图，既要求1到所有的点的距离又要求其他所有点到1的距离，由于只学过spfa算法，就又用了spfa算法，求1到其他点的距离比较好求，但其他点到1的距离就不太好求了,我用到了图的转置，就是把所有的边的方向都反向，给建立一个新的图，这样1以外的点到1的距离就是1到1以外的点的距离；
用习惯了Java还真不习惯c++，特别是看到指针就烦，但Java这时间也真吓人的，
AC代码： time: 21282ms 好可怕！
import java.util.*;
import java.io.*; public class Main {
public static Ver[] array1;
public static Ver[] array2;
public static int[] head1;
public static int[] head2;
public static int n;
public static long[] dis1;
public static long[] dis2;
public static boolean[] judge;
public static long Max = ;
public static long[] result;
public static int count; /**
* @param args
*/
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
Scanner s = new Scanner(new BufferedInputStream(System.in));
int t = s.nextInt(); while (t-- > ) { n = s.nextInt();
int m = s.nextInt();
array1 = new Ver[];
array2 = new Ver[];
head1 = new int[n + ];
head2 = new int[n + ];
count = ;
for (int i = ; i < m; i++) { //建图
int a = s.nextInt();
int b = s.nextInt();
long c = s.nextLong();
array1[count] = new Ver(b, c); //正图
array1[count].next = head1[a];
head1[a] = count; array2[count] = new Ver(a, c); //反图
array2[count].next = head2[b];
head2[b] = count;
count++;
}
result = new long[n + ];
spfa1();
spfa2();
long ans = ;
for (int i = ; i <= n; i++) { //求和
ans += dis1[i] + dis2[i];
}
System.out.println(ans);
}
s.close();
} public static void spfa2(int a) { //反向图的spfa算法
dis2 = new long[n + ];
judge = new boolean[n + ];
for (int i = ; i < n + ; i++) {
dis2[i] = Max; }
LinkedList<Integer> queue = new LinkedList<Integer>();
judge[] = true;
dis2[] = ;
queue.add();
while (!queue.isEmpty()) {
int vpoll = queue.poll();
judge[vpoll] = false; int temp = head2[vpoll];
while (temp != ) {
if (relax2(vpoll, array2[temp].value, array2[temp].distance)) {
if (!judge[array2[temp].value]) {
judge[array2[temp].value] = true;
queue.add(array2[temp].value);
}
}
temp = array2[temp].next;
}
} } public static void spfa1(int a) { //正向图的spfa算法
dis1 = new long[n + ];
judge = new boolean[n + ];
for (int i = ; i < n + ; i++) {
dis1[i] = Max; }
LinkedList<Integer> queue1 = new LinkedList<Integer>();
judge[a] = true;
dis1[a] = ;
queue1.add(a);
while (!queue1.isEmpty()) {
int vpoll = queue1.poll();
judge[vpoll] = false; int temp = head1[vpoll];
while (temp != ) {
if (relax1(vpoll, array1[temp].value, array1[temp].distance)) {
if (!judge[array1[temp].value]) {
judge[array1[temp].value] = true;
queue1.add(array1[temp].value);
}
}
temp = array1[temp].next;
}
} } public static boolean relax1(int a, int b, long c) { if (dis1[a] + c < dis1[b]) {
dis1[b] = dis1[a] + c;
return true;
}
return false;
} public static boolean relax2(int a, int b, long c) { if (dis2[a] + c < dis2[b]) {
dis2[b] = dis2[a] + c;
return true;
}
return false;
} } class Ver { //图类
long distance;
int value;
int next; Ver(int value, long distance) {
this.value = value;
this.distance = distance;
}
}