学步园

题意： 给一副有向图，问源点到其他的距离和其他点到源点的距离之和。

解法： 建两幅图，另一幅图的边全部相反，然后用dijkstra求两遍源点到其他点的最短路即可。

北大的这题会卡vector，TLE6次后怒改手写邻接表，然后1.9sAC- -！！

然后是题目说好的权值和不大于1e9，但是但是，显而易见，answer是可以大于权值和的，必须lld。。。。

相当的无语啊

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef __int64 lld;
typedef pair <int,int> P;
const int INF = ~0u>>1;
const int MOD = 1e9+7;
#define CIN(x) scanf("%d", &x)
#define clr(a,b) memset(a, b, sizeof(a))
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define PB push_back
#define MP make_pair

const int MAXN = 1000010;
int n;
int dis[MAXN];
int vis[MAXN];
struct POINT {
    int to,w;
    POINT (){}
    POINT (int a, int c) : to(a), w(c) {}
    bool operator < (const POINT &tt) const {
        return dis[to] > dis[tt.to];
    }
};
priority_queue <POINT> que;
struct E {
    int to,w,next;
}edge[MAXN],edge2[MAXN];
int head[MAXN],head2[MAXN];
int tot,tot2;

void add_edge(int u, int v, int w) {
    edge[tot].next = head[u];
    edge[tot].to = v;
    edge[tot].w = w;
    head[u] = tot ++;

    edge2[tot2].next = head2[v];
    edge2[tot2].to = u;
    edge2[tot2].w = w;
    head2[v] = tot2 ++;
}

lld dijkstra(int s) {
    FOR(i,1,n) dis[i] = INF,vis[i] = 0;
    dis[s] = 0;
    while(!que.empty()) que.pop();
    que.push(POINT(s,0));

    while(!que.empty()) {
        POINT f = que.top(); que.pop();
        if(vis[f.to]) continue;
        vis[f.to] = 1;
        int v = f.to;
        for(int p=head[v]; p!=-1; p=edge[p].next) {
            E e = edge[p];
            if(dis[v] + e.w < dis[e.to]) {
                dis[e.to] = dis[v] + e.w;
                que.push(POINT(e.to,dis[e.to]));
            }
        }
    }
    lld ret = 0;
    FOR(i,1,n) ret += (lld)dis[i];
    return ret;
}

lld dijkstra2(int s) {
    FOR(i,1,n) dis[i] = INF,vis[i] = 0;
    dis[s] = 0;
    while(!que.empty()) que.pop();
    que.push(POINT(s,0));

    while(!que.empty()) {
        POINT f = que.top(); que.pop();
        if(vis[f.to]) continue;
        vis[f.to] = 1;
        int v = f.to;
        for(int p=head2[v]; p!=-1; p=edge2[p].next) {
            E e = edge2[p];
            if(dis[v] + e.w < dis[e.to]) {
                dis[e.to] = dis[v] + e.w;
                que.push(POINT(e.to,dis[e.to]));
            }
        }
    }
    lld ret = 0;
    FOR(i,1,n) ret += (lld)dis[i];
    return ret;
}

int main() {
    int cas;
    int m;
    CIN(cas);
    while(cas--) {
        clr(head, -1);
        clr(head2, -1);
        tot = tot2 = 0;
        scanf("%d%d", &n, &m);
        int a,b,c;
        while(m--) {
            scanf("%d%d%d", &a, &b, &c);
            add_edge(a,b,c);
        }
        lld ans = dijkstra(1) + dijkstra2(1);
        printf("%I64d\n", ans);
    }
    return 0;
}