题目链接：http://poj.org/problem?id=1511
题意：给出n个点和n条有向边，求所有点到源点1的来回最短路之和（保证每个点都可以往返源点1）
题目比较简单就是边和点的个数有点多所以可以用dijstra+优先队列这样复杂度就可以到v*logn
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#define inf 1000000000
using namespace std;
const int M = 1e6 + 10;
int n , m , a[M] , b[M] , c[M] , dis[M];
struct TnT {
int v , w;
};
struct cmp {
bool operator() (int x , int y) {
return dis[x] > dis[y];
}
};
vector<TnT>vc[M];
bool vis[M];
void dij(int s) {
priority_queue<int , vector<int> , cmp>q;
memset(vis , false , sizeof(vis));
TnT gg;
q.push(s);
dis[s] = 0;
while(!q.empty()) {
int m = q.top();
vis[m] = true;
for(int i = 0 ; i < vc[m].size() ; i++) {
gg = vc[m][i];
if(dis[m] + gg.w < dis[gg.v]) {
dis[gg.v] = dis[m] + gg.w;
if(!vis[gg.v]) {
vis[gg.v] = true;
q.push(gg.v);
}
}
}
q.pop();
}
}
int main() {
int t;
TnT gg;
scanf("%d" , &t);
while(t--) {
scanf("%d%d" , &n , &m);
for(int i = 1 ; i <= n ; i++) {
vc[i].clear();
dis[i] = inf;
}
for(int i = 1 ; i <= m ; i++) {
scanf("%d%d%d" , &a[i] , &b[i] , &c[i]);
gg.v = b[i] , gg.w = c[i];
vc[a[i]].push_back(gg);
}
dij(1);
long long sum = 0;
for(int i = 1 ; i <= n ; i++) {
sum += (long long)dis[i];
}
for(int i = 1 ; i <= n ; i++) {
vc[i].clear();
dis[i] = inf;
}
for(int i = 1 ; i <= m ; i++) {
gg.v = a[i] , gg.w = c[i];
vc[b[i]].push_back(gg);
}
dij(1);
for(int i = 1 ; i <= n ; i++) {
sum += (long long)dis[i];
}
printf("%lld
" , sum);
}
return 0;
}