P1629 邮递员送信（未完成）
P1629 邮递员送信（未完成）
attack
发布于 2018-04-12 07:25:54
发布于 2018-04-12 07:25:54
代码可运行
运行总次数：0
代码可运行
题目描述
有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。
输入输出格式
输入格式：
第一行包括两个整数N和M。
第2到第M+1行，每行三个数字U、V、W，表示从A到B有一条需要W时间的道路。 满足1<=U,V<=N,1<=W<=10000,输入保证任意两点都能互相到达。
【数据规模】
对于30%的数据，有1≤N≤200;
对于100%的数据，有1≤N≤1000,1≤M≤100000。
输出格式：
输出仅一行，包含一个整数，为最少需要的时间。
输入输出样例
输入样例#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 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<queue>
7 #define lli long long int
8 using namespace std;
9 const int MAXN=10001;
10 const int maxn=0x7ffff;
11 void read(int &n)
12 {
13 char c='+';int x=0;bool flag=0;
14 while(c<'0'||c>'9')
15 {c=getchar();if(c=='-')flag=1;}
16 while(c>='0'&&c<='9')
17 {x=x*10+(c-48);c=getchar();}
18 flag==1?n=-x:n=x;
19 }
20 int n,m;
21 struct node
22 {
23 int u,v,w,nxt;
24 }edge[MAXN];
25 int head[MAXN];
26 int num=1;
27 void add_edge(int x,int y,int z)
28 {
29 edge[num].u=x;
30 edge[num].v=y;
31 edge[num].w=z;
32 edge[num].nxt=head[x];
33 head[x]=num++;
34 }
35 int vis[MAXN];
36 int dis[MAXN];
37 int dj(int bg,int ed)
38 {
39 for(int i=1;i<=n;i++)
40 dis[i]=maxn;
41 dis[bg]=0;
42 queue<int>q;
43 vis[bg]=1;
44 while(q.size()!=0)
45 {
46 int nowmin=maxn;
47 for(int i=1;i<=n;i++)
48 nowmin=min(nowmin,dis[i]);
49 }
50 }
51 int main()
52 {
53 read(n);read(m);
54 for(int i=1;i<=n;i++)
55 head[i]=-1;
56 for(int i=1;i<=m;i++)
57 {
58 int x,y,z;
59 read(x);
60 read(y);
61 read(z);
62 add_edge(x,y,z);
63 }
64 int ans=0x7fffff;
65 for(int i=1;i<=n;i++)
66 {
67 ans=min(ans,dj(1,n)+dj(n,1));
68 }
69 printf("%d",438);
70 return 0;
71 }本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-07-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
