题目描述

有一个邮递员要送东西，邮局在节点1。他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的。共有M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。

输入格式

输入文件第一行包含一个正整数N和M ； 接下来M行，每行三个正整数U,V,W，表示该条道路为从U到V的，且通过这条道路需要W的时间。满足1≤U,V≤N，1≤W≤ 10000，输入保证任意两点都能互相到达。

输出格式

输出仅一行，包含一个整数，为最少需要的时间。

样例输入

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

样例输出

83

数据规模

对于30%的数据，满足1≤N≤200； 对于100%的数据，满足1≤N≤1000，1≤M≤100000。

题目分析

起点->每一个点->起点 可以转化为 起点->每一个点+(反图)起点->每一个点

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=20005; struct Edge { int from,to,dist; }; struct Spfa { int n,m; vector<Edge>edges; vector<int>G[maxn]; bool inque[maxn]; int dist[maxn],used[maxn],path[maxn]; void init(int n) { this->n=n; edges.clear(); for(int i=1; i<=n; i++)G[i].clear(); } void AddEdge(int from,int to,int dist) { edges.push_back((Edge) { from,to,dist }); m=edges.size(); G[from].push_back(m-1); } bool main(int s) { for(int i=1; i<=n; i++)dist[i]=0x7fffffff/2; memset(inque,0,sizeof(inque)); deque<int>Q; Q.push_back(s); dist[s]=0; path[s]=s; inque[s]=1; used[s]++; while(!Q.empty()) { int Now=Q.front(); Q.pop_front(); inque[Now]=0; for(int i=0; i<G[Now].size(); i++) { Edge& e=edges[G[Now][i]]; int Next=e.to; if(dist[Next]>dist[Now]+e.dist) { dist[Next]=dist[Now]+e.dist; path[Next]=Now; if(!inque[Next]) { used[Next]++; if(used[Next]==edges.size())return false; //负权回环 if(!Q.empty()&&dist[Next]<dist[Q.front()])Q.push_front(Next); //SLF优化 else Q.push_back(Next); inque[Next]=1; } } } } return true; } void Output(int x) { if(path[x]==x) { cout<<x<<" "; return; } Output(path[x]); cout<<x<<" "; } }; Spfa spfa1,spfa2; int n,m,ans=0; int main() { n=Get_Int(); m=Get_Int(); spfa1.init(n); spfa2.init(n); for(int i=1; i<=m; i++) { int x=Get_Int(),y=Get_Int(),v=Get_Int(); spfa1.AddEdge(x,y,v); spfa2.AddEdge(y,x,v); } spfa1.main(1); spfa2.main(1); for(int i=1; i<=n; i++)ans+=spfa1.dist[i]+spfa2.dist[i]; printf("%d\n",ans); return 0; }