学步园

小记：这题还是要理解了题意就好做了，这题之前做过一次。

题意：从一点送请柬到其它n-1个点，然后再回来的最小路程。

思路：去送的最小路程就是单源最短路径，

而回来，想一下就可以知道，因为图是有向图，所以将图反向之后，那么我到其它n-1个点的最短路径就是他们到我的最短路径了。

因此反向一次在进行一次spfa，将总共两次的spfa的最短距离相加起来就是answer了。

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define REP(a,b,c) for(int a = b; a < c; ++a)
#define eps 10e-8
#define DEBUG printf("here\n");

const int MAX_ = 1000010;
const int N = 100010;
const int INF = 0x7fffffff;

int n;

struct node{
    int u, v;
    int cap, next;
}edge[MAX_*2];

struct point{
    int x,y,cap;
}p[MAX_];

int H[MAX_*2];
//int V[MAX_*2];
int d[MAX_];
bool vis[MAX_];
int m, cnt, M;

void add(int u, int v, int cap)
{
    edge[M].u = u;
    edge[M].v = v;
    edge[M].cap = cap;
    edge[M].next = H[u];
    H[u] = M++;
}

void spfa(int start)
{
    queue<int > q;
    REP(i, 0, n+1){
        vis[i] = 0;
        d[i] = INF;
    }
    vis[start] = 1;
    d[start] = 0;
    q.push(start);

    while(!q.empty()){
        int cur = q.front(); q.pop();

        vis[cur] = 0;

        for(int i = H[cur]; i+1; i = edge[i].next){
            int v = edge[i].v;
            int u = edge[i].u;
            if(d[v] > d[u] + edge[i].cap){
                d[v] = d[u] + edge[i].cap;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);

                }
            }
        }

    }

    return ;
}


int main(){
	int T, ss, tt, v, s, t;
	char str[10];
	scanf("%d", &T);

	while(T-- && scanf("%d%d", &n, &m)){
	    //scanf("%d", &m);

        //mst(g, -1);

        mst(H, -1);
        //mst(V, -1);

        M = 0;
        REP(i, 0, m){
            scanf("%d%d%d", &s, &t, &v);
            add(s,t,v);
            p[i].x = s;
            p[i].y = t;
            p[i].cap = v;
        }
        spfa(1);
        int sum = 0;
        REP(i, 1, n+1){
            sum += d[i];
        }

        mst(H, -1);
        //mst(V, -1);
        M = 0;
        REP(i, 0, m){
            add(p[i].y, p[i].x, p[i].cap);
        }

        spfa(1);
        REP(i, 1, n+1){
            sum += d[i];
        }
/*
        REP(i, 0, n)REP(j, 0, n){
            printf("%.3f ", g[i][j]);
            if(j == n-1)printf("\n");
        }*/

        printf("%d\n", sum);



	}
	return 0;
}