有一个邮递员要送东西,邮局在节点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到其他点的最短路的长度,
然后把所有边反向储存。
再求一边
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=100001;
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*4];
25 int head[MAXN];
26 int num=1;
27 int x[MAXN],y[MAXN],z[MAXN];
28 void add_edge(int x,int y,int z)
29 {
30 edge[num].u=x;
31 edge[num].v=y;
32 edge[num].w=z;
33 edge[num].nxt=head[x];
34 head[x]=num++;
35 }
36 int vis[MAXN];
37 int dis[MAXN];
38 void dj(int bg)
39 {
40 for(int i=1;i<=n;i++)
41 dis[i]=maxn;
42 dis[bg]=0;
43 queue<int>q;
44 memset(vis,0,sizeof(vis));
45 q.push(1);
46 for(int i=1;i<=n;i++)
47 {
48 int nowmin=maxn;
49 int pos=-1;
50 for(int i=1;i<=n;i++)
51 {
52 if(vis[i]==0&&dis[i]<nowmin)
53 {
54 pos=i;
55 nowmin=dis[i];
56 }
57 }
58 vis[pos]=1;
59 for(int i=head[pos];i!=-1;i=edge[i].nxt)
60 {
61 int will=edge[i].v;
62 if(dis[will]>dis[edge[i].u]+edge[i].w)
63 dis[will]=dis[edge[i].u]+edge[i].w;
64 }
65 }
66 }
67 int main()
68 {
69 read(n);read(m);
70 for(int i=1;i<=n;i++)
71 head[i]=-1;
72 for(int i=1;i<=m;i++)
73 {
74
75 read(x[i]);
76 read(y[i]);
77 read(z[i]);
78 add_edge(x[i],y[i],z[i]);
79 }
80 int ans=0;
81 dj(1);
82 int ans2=0;
83 for(int i=1;i<=n;i++)
84 ans+=dis[i];
85 for(int i=1;i<=n;i++)
86 head[i]=-1;
87 num=1;
88 for(int i=1;i<=m;i++)
89 add_edge(y[i],x[i],z[i]);
90 dj(1);
91 for(int i=1;i<=n;i++)
92 ans+=dis[i];
93 printf("%d",ans);
94 return 0;
95 }