差旅花费

问题描述

有n个车站，其中1号车站为始发站，现有n-1个人，你需要安排他们分别去往除始发站以外的n-1个车站，然后返回始发站。交通系统的所有路径均为单向路径，连接两个不同的车站，每经过一条路径需要交纳一定的费用，你能求出总花费的最低金额嘛

输入格式

第一行一个整数T，表示测试用例的个数。
对于每个测试用例，输入格式如下
第一行两个整数n,m,分别表示车站的数量和车站之间的单向路径数。
接下来m行，每行三个数s,e,c,表示存在从s到e的单向路径，花费为c

输出格式

对于每个测试用例，输出其总花费的最低金额，每个测试用例的输出占一行。

样例输入

样例输出

46
210

数据规模和约定

1<=n,m<=1000000
价格c为正整数，且保证其总和小于1000000000

#include <bits/stdc++.h>
using namespace std;
int t, n, m, s, e, c, dis[2000005], vis[2000005], head[2000005], head2[2000005];
int tot = 0, tot2 = 0;  // 当前边的总数
struct edge {
    int u, v, w, next;
} edges[2000005], edges2[2000005];

void addEdge(int u, int v, int w) {  // 加一条边
    edges[tot].u = u, edges[tot].v = v, edges[tot].next = head[u], edges[tot].w = w;
    head[u] = tot++;
}

void addEdge2(int u, int v, int w) {  // 加一条边
    edges2[tot2].u = u, edges2[tot2].v = v, edges2[tot2].next = head2[u], edges2[tot2].w = w;
    head2[u] = tot2++;
}

void spfa(int s, int head[], edge edges[]) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    dis[s] = 0;
    q.emplace(s);
    vis[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i != -1; i = edges[i].next) {
            int &v = edges[i].v, newdis = dis[u] + edges[i].w;
            if (dis[v] > newdis) {
                dis[v] = newdis;
                if (!vis[v]) {
                    vis[v] = 1;
                    q.emplace(v);
                }
            }
        }
    }
}

int main() {
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        memset(head, -1, sizeof(head));  // 储存每个节点的第一条边的编号，-1表示没有边
        memset(head2, -1, sizeof(head2));
        scanf("%d%d", &n, &m);
        for (int j = 0; j < m; j++) {
            scanf("%d%d%d", &s, &e, &c);
            addEdge(s, e, c);
            addEdge2(e, s, c);
        }
        int ans = 0;
        spfa(1, head, edges);
        for (int i = 2; i <= n; ++i)
            ans += dis[i];
        spfa(1, head2, edges2);
        for (int i = 2; i <= n; ++i)
            ans += dis[i];
        printf("%d\n", ans);
    }
    return 0;
}