本文共 2029 字，大约阅读时间需要 6 分钟。
给定一个 nn 点 mm 边的有向带权图表示一座城市，起点为 11 。送餐小哥需要给 nn 个客户送外卖，第 ii 个客户的家在第 ii 号点。由于他的车子容量很小，所以一次只能容纳一份外卖，所以送达外卖之后就要回到起点取新的外卖送下一单，直到全部送到位置。
有向图保证联通。外卖小哥一定走的最短路。
求送餐小哥走的总路程。
第一行一个整数 TT，表示数据组数。
对于每组数据，第一行两个整数 nn 和 mm 。
接下来 mm 行，每行三个整数 u_i,v_i,c_iui,vi,ci 表示每条有向边。
对于每组数据，输出一行一个整数表示答案。
对于 20\%20% 的数据： 0 < n \leq 1000<n≤100 ,
对于 40\%40% 的数据： 0 < n \leq 3000<n≤300 ,
对于 60\%60% 的数据： 0 < n \leq 10000<n≤1000 ,
对于 100\%100% 的数据： 0 < n \leq 20000, m \leq 60000, 1\le T\le 10,0\le c_i\le 10^9,1\le u_i,v_i\le n0<n≤20000,m≤60000,1≤T≤10,0≤ci≤109,1≤ui,vi≤n
保证答案在 `long long` 范围内。
样例输入复制
22 21 2 132 1 334 61 2 102 1 601 3 203 4 102 4 54 1 50
样例输出复制
46210
看这个数据量跑dijkstra应该会超，，直接跑spfa，，
一次只能送一顿外卖，，送完还要回到起点，，先从起点1开始正向建图，，可以得到1到任意点的最短距离，，在从任意点到起点1反向建图，，跑两遍dijkstra，，注意longlong，，欧了。
#includeusing namespace std;typedef long long ll;const ll inf=0x3f3f3f3f3f3f3f3f;const int maxn=2e4+10;const int maxm=6e4+10;int head[maxn],cnt,from[maxm],to[maxm];int n,m;bool vis[maxn];ll dis[maxn],cost[maxm];struct Edge{ int u,v,next; ll w;}edge[maxm];void addedge(int u,int v,ll w){ edge[cnt].u=u; edge[cnt].v=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;}void spfa(int s){ for(int i=1;i<=n;i++){ vis[i]=false; dis[i]=inf; } queue q; q.push(s); dis[s]=0; vis[s]=true; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=false; for(int i=head[u];i!=-1;i=edge[i].next) { if(dis[edge[i].v]>dis[u]+edge[i].w) { dis[edge[i].v]=dis[u]+edge[i].w; if(!vis[edge[i].v]) { vis[edge[i].v]=true; q.push(edge[i].v); } } } }}int main(){ int T; ios::sync_with_stdio(false); cin>>T; while(T--) { cnt=0; cin>>n>>m; for(int i=1;i<=n;i++) head[i]=-1; for(int i=1;i<=m;i++) { cin>>from[i]>>to[i]>>cost[i]; addedge(from[i],to[i],cost[i]); } spfa(1); ll ans=0; for(int i=1;i<=n;i++) ans+=dis[i]; cnt=0; for(int i=1;i<=n;i++) head[i]=-1; for(int i=1;i<=m;i++) addedge(to[i],from[i],cost[i]); spfa(1); for(int i=1;i<=n;i++) ans+=dis[i]; cout< <
转载地址：http://jxyzi.baihongyu.com/