Invitation Cards

反向建图

单纯的反向建图，求dij就可以了。
我刚开始认为，可以两个人一起乘车花一人的钱。求成最小生成树了。

代码

#include<iostream>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll inf = 2e9 + 10;
const int max_m = 1e6 + 100;
const int max_n = 1e6 + 100;
struct edges{
    int u, v;ll cost;
}ES[max_m];
struct edge{
    int to;ll cost;
    int next;
}E[max_m << 1];
int head[max_n];
int cnt = 1;
void add(int from,int to,ll cost){
    E[cnt].to = to;E[cnt].cost = cost;
    E[cnt].next = head[from];
    head[from] = cnt++;
}
ll d[max_n];
ll dijistra(int s,int n) {
    fill(d, d + n + 10, inf);
    priority_queue<pll, vector<pll>, greater<pll> > que;
    d[s] = 0;que.push(pll(d[s], s));
    while (!que.empty()) {
        pll p = que.top();que.pop();
        ll dist = p.first;ll u = p.second;
        if (dist > d[u])continue;
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (d[e.to] > d[u] + e.cost) {
                d[e.to] = d[u] + e.cost;
                que.push(pll(d[e.to], e.to));
            }
        }
    }ll sum = 0;
    for (int i = 1;i <= n;++i)sum += (ll)d[i];
    return sum;
}
int main() {
    int T;scanf("%d", &T);
    while (T--) {
        int N, M;
        scanf("%d %d", &N, &M);
        fill(head, head + N + 10, 0);cnt = 1;
        for (int i = 1;i <= M;++i) {
            scanf("%d %d %lld", &ES[i].u, &ES[i].v, &ES[i].cost);
            add(ES[i].u, ES[i].v, ES[i].cost);
        }ll res = dijistra(1, N);
        fill(head, head + N + 10, 0);cnt = 1;
        for (int i = 1;i <= M;++i)
            add(ES[i].v, ES[i].u, E[i].cost);
        res += dijistra(1, N);
        printf("%lld\n", res);
    }
}