题目描述
有一个邮递员要送东西，邮局在节点 111。他总共要送 n−1n-1n−1 样东西，其目的地分别是节点 222 到节点 nnn。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 mmm 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n−1n-1n−1 样东西并且最终回到邮局最少需要的时间。 输入格式
第一行包括两个整数，nnn 和 mmm，表示城市的节点数量和道路数量。
第二行到第 (m+1)(m+1)(m+1) 行，每行三个整数，u,v,wu,v,wu,v,w，表示从 uuu 到 vvv 有一条通过时间为 www 的道路。 输出格式
输出仅一行，包含一个整数，为最少需要的时间。 输入输出样例 输入 #1
5 10 2 3 5 1 5 5 3 5 6 1 2 8 1 3 8 5 3 4 4 1 8 4 5 3 3 5 6 5 4 2
输出 #1
83
说明/提示
对于 30%30%30% 的数据，1≤n≤2001 \leq n \leq 2001≤n≤200。
对于 100%100%100% 的数据，1≤n≤1031 \leq n \leq 10^31≤n≤103，1≤m≤1051 \leq m \leq 10^51≤m≤105，1≤u,v≤n1\leq u,v \leq n1≤u,v≤n，1≤w≤1041 \leq w \leq 10^41≤w≤104，输入保证任意两点都能互相到达。
#include <iostream> #include <algorithm> #include <climits> #include <cstdio> #include <cstring> #include <cmath> #include <queue> using namespace std; const int inf = 1e9 + 100; const int maxn = 2e3 + 10; const int maxv = 1e5 + 10; struct node{ int v; int len, nex; }edge[maxv << 1]; struct value{ int id; int val; value(int _id = 0, int _val = 0) { id = _id, val = _val; } }; int head[maxn]; bool vis[maxn]; int d[maxn]; int cnt; int n, m; void add_edge(int u, int v, int val) { edge[++cnt].v = v; edge[cnt].nex = head[u]; edge[cnt].len = val; head[u] = cnt; } bool operator < (value x, value y) { return x.val > y.val; } void Dijkstra(int s) { memset(vis, 0, sizeof(vis)); fill(d, d + maxn, inf); d[s] = 0; priority_queue<value>que; que.push(value(s, 0)); while(!que.empty()) { value cur = que.top(); que.pop(); if(vis[cur.id] == true) continue; vis[cur.id] = true; int id = cur.id; for(int i = head[id]; i; i = edge[i].nex) { int v = edge[i].v; if(d[v] > d[id] + edge[i].len) { d[v] = d[id] + edge[i].len; que.push(value(v, d[v])); } } } } int main() { int u, v, w; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { scanf("%d%d%d", &u, &v, &w); add_edge(u, v, w); add_edge(v + n, u + n, w); } int ans = 0; Dijkstra(1); for(int i = 2; i <= n; i++) ans += d[i]; Dijkstra(n + 1); for(int i = n + 1; i <= 2 * n; i++) ans += d[i]; printf("%d\n", ans); return 0; }