题目链接：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 1000000000using 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\n" , sum);    }    return 0;    }

poj 1511 Invitation Cards（dijstra优化）