首页 > 代码库 > P1629 邮递员送信（未完成）
P1629 邮递员送信（未完成）
题目描述
有一个邮递员要送东西，邮局在节点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 102 3 51 5 53 5 61 2 81 3 85 3 44 1 84 5 33 5 65 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 node22 {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 }
P1629 邮递员送信（未完成）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。