反向建图
单纯的反向建图,求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); } }