游客 注册 | 登录
中文 | En

1923 - 邮递员送信

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

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

题目输入

第一行：N M
接下来M行，每行三个正整数U、V、W，表示该条道路为从U到V的，且通过这条道路需要W的时间。满足1 <= U，V <= N <= 1000，1 <= W <= 100000，输入保证任意两点都能互达。

题目输出

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

输入/输出样例

输入格式

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

C++解答

#include<bits/stdc++.h>
using namespace std;

const int N=2*1005;
const int M=2*1e5+100;
int ans,n;
int to[M],h[N],w[M],nxt[M],tot,dis[N],vis[N]; 
void add(int a, int b, int c){
	to[++tot]=b,w[tot]=c,nxt[tot]=h[a],h[a]=tot;
} 
 
void Dijkstra(int s){
	priority_queue<pair<int,int> > q;
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push({0,s});
	while(!q.empty()){
	     pair<int,int> k=q.top();
	     q.pop();
	     int v=k.second;
	     if(vis[v]) continue;
	     vis[v]=1;
	     for(int i=h[v]; i!=0; i=nxt[i]){
	     	 int u=to[i];
	     	 if(dis[v]+w[i]<dis[u]){
	     	 	dis[u]=dis[v]+w[i];
	     	 	q.push({-dis[u],u});
			 }
		 }
	}
}
int main()
{
	int c,u,v,w,m;
	cin>>n>>m;
	for(int i=1; i<=m; i++){
		cin>>u>>v>>w;
		add(u,v,w);
		add(v+n,u+n,w);//反向建边 
	}
	Dijkstra(1);
	for(int i=2; i<=n; i++){
		ans+=dis[i];
	}
	Dijkstra(1+n);
	for(int i=n+2; i<=2*n; i++){
		ans+=dis[i];
	}
	cout<<ans<<endl;
	return 0;
}
请先登陆