投递员送信

P1629 邮递员送信(未产生),p1629送信

P1629 邮递员送信,p1629邮递员送信

P1629 邮递员送信

难点陈述

有三个邮递员要送东西,邮局在节点1.他一同要送N-1样东西,其目标地分别是2~N。由于这几个城邑的直通相比较辛勤,由此全部的道路都以单行的,共有M条道路,通过每条道路须要一定的时光。这一个邮递员每一遍只好带同样东西。求送完那N-1样东西还要最终回到邮局最少须要有些时间。

标题陈诉

有多个邮递员要送东西,邮局在节点1.他合计要送N-1样东西,其指标地分别是2~N。由于那么些都市的畅通相比艰难,因而具备的征程都是单行的,共有M条道路,通过每条道路需求料定的时间。这些邮递员每一次只可以带同样东西。求送完那N-1样东西还要最后回到邮局最少须要有些时间。

主题材料陈说

有八个邮递员要送东西,邮局在节点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<=一千0,输入保险自由两点都能互相达到。

【数据规模】

对于30%的数据,有1≤N≤200;

对于100%的数据,有1≤N≤1000,1≤M≤100000。

 

出口格式:

 

出口仅一行,包含多个板寸,为至少要求的年月。

 

输入输出格式

输入格式:

 

率先行饱含八个整数N和M。

第2到第M+1行,每行八个数字U、V、W,表示从A到B有一条需求W时间的征程。
满意1<=U,V<=N,1<=W<=一千0,输入保证自由两点都能互相达到。

【数据规模】

对于30%的数据,有1≤N≤200;

对于100%的数据,有1≤N≤1000,1≤M≤100000。

 

出口格式:

 

出口仅一行,包蕴多少个整数,为至少供给的年华。

 

输入输出格式

输入格式:

 

率先行满含多个整数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 }

 

邮递员送信(未到位),p1629送信 标题汇报有二个邮递员要送东西,邮局在节点1.他合计要送N-1样东西,其指标地分别是2~N。由于这些…

输入输出样例

输入样例#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 }

 

 

邮递员送信,p1629邮递员送信 标题汇报有三个邮递员要送东西,邮局在节点1.他一起要送N-1样东西,其指标地分别是2~N。由于这些都市…

输入输出样例

输入样例#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


思路:
spfa挺水的一道题,最开始看到这个题的时候没有看清是单行道,就感觉跑一遍最短路然后再乘2就行了。
结果她是单向边,然后就想我们这个题说白了就是求从1点到其他n-1个点的最短路,然后再加上从其他n-1个点到1点的最短路之和,然后就想到用Floyd,这样我们就可以轻易的的到其他n-1个点到1的最短路,行,你就用Floyd做吧,不T乘狗才怪呢、、
好,那又想到,既然用Floyd会T,那就用spfa吧,我们跑n遍spfa不就吧他们都弄出来了吗?!是,恭喜,再次T成狗、、、
我们想一个现实一点的做法,我们现在是要求两步,第一步是要求从1到其他n-1个点的最短路,直接spfa就行,第二问是要求从其他n-1个点到1点的最短路径,我们考虑建反向边,再用spfa跑一遍从1到n-1不就好了,怎么建反向边?!我们那个结构体存一下不就好了。。。为什么要建反向边就可以解决问题??因为这个地方我们考虑从n-1个点到1不跟从1到n-1个点一样吗,就是他的路是单向的,我们现在只可以走得便反向减回去不就好了、、、

代码:

#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100000
#define maxn 99999999
using namespace std;
long long ans;
int n,m,x,y,z,s,tot,dis[N],head[N];
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct NN
{
    int x,y,z;
}edde[N];
struct Edge
{
    int to,dis,from,next;
}edge[N];
int add(int x,int y,int z)
{
    tot++;
    edge[tot].to=y;
    edge[tot].dis=z;
    edge[tot].next=head[x];
    head[x]=tot;
}
int spfa(int s)
{
    queue<int>q;  bool vis[N]; int sum=0;
    for(int i=1;i<=n;i++) dis[i]=maxn,vis[i]=false;
    q.push(s);vis[s]=true;dis[s]=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        for(int i=head[x];i;i=edge[i].next)
        {
            int t=edge[i].to;
            if(dis[t]>dis[x]+edge[i].dis)
            {
                dis[t]=dis[x]+edge[i].dis;
                if(!vis[t])
                {
                    q.push(t);
                    vis[t]=true;
                }
            }
        }
        vis[x]=false;
    }
    for(int i=2;i<=n;i++)
     sum+=dis[i];
    return sum;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        x=read(),y=read(),z=read();
        add(x,y,z);
        edde[i].x=x;edde[i].y=y,edde[i].z=z;
    }
    ans+=spfa(1); s=tot,tot=0;
    memset(dis,0,sizeof(dis));
    memset(head,0,sizeof(head));
    memset(edge,0,sizeof(edge));
    for(int i=1;i<=s;i++)
      add(edde[i].y,edde[i].x,edde[i].z);
    ans+=spfa(1);
    printf("%lld",ans);
    return 0;
}

 

Post Author: admin

发表评论

电子邮件地址不会被公开。 必填项已用*标注