题目描述

有一个邮递员要送东西,邮局在节点$1$。他总共要送$n−1$样东西,其目的地分别是节点 $2$ 到节点$n$。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有$m$条道路。这个邮递员每次只能带一样东西,并且运送每件物品过后必须返回邮局。求送完这 $n-1$样东西并且最终回到邮局最少需要的时间。

$1\leq n\leq 10^3$,$1\leq m\leq 10^5$

$50pts$

我们先做一遍dij,求出$1$号节点到其他节点的最短距离,再做$n-1$遍dij,求出$i$号节点到1号节点的距离,最后统计答案。
Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef pair<int,int> P;
int n,m,Last[N],tot;
struct node
{
int to,v,Next;
}edge[N];
int dis[N];
bool mark[N];
priority_queue<P,vector<P>,greater<P> >q;
void dij(int s)
{
memset(mark,0,sizeof(mark));
for(int i=1;i<=n;i++)dis[i] = ((1 << 31) - 1);
dis[s] = 0;
q.push(make_pair(dis[s],s));
while(!q.empty())
{
int u = q.top().second,v = q.top().first;q.pop();
if(mark[u])continue;
mark[u] = true;
for(int i=Last[u];i;i=edge[i].Next)
{
int k = edge[i].to;
if(mark[k])continue;
if(dis[k] > dis[u] + edge[i].v)
{
dis[k] = dis[u] + edge[i].v;
q.push(make_pair(dis[k],k));
}
}
}
}
void add(int x,int y,int v){edge[++tot].to = y,edge[tot].v = v,edge[tot].Next = Last[x],Last[x] = tot;}
int main()
{
int s;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
add(x,y,z);
}
dij(1);
long long ans = 0;
for(int i=2;i<=n;i++)ans += dis[i];
for(int i=2;i<=n;i++)
{
dij(i);
ans += dis[1];
}
printf("%lld",ans);
return 0;
}

记录详情

$70pts$

在$50pts$的基础上加一个快读+O2;

$100pts$

我们在处理$2~n$个点到1号点的距离时,我们可以建一个反向边,然后再跑一边dij,就可以了。
Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef pair<int,int> P;
int n,m,Last[N],tot,x[N],y[N],z[N];
int read()
{
char c = getchar();
int x = 0,f = 1;
while(c < '0' || c > '9')
{
if(c == '-')f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + (c - '0');
c = getchar();
}
return f * x;
}
struct node
{
int to,v,Next;
}edge[N];
int dis[N];
bool mark[N];
void dij(int s)
{
priority_queue<P,vector<P>,greater<P> >q;
memset(mark,0,sizeof(mark));
for(int i=1;i<=n;i++)dis[i] = ((1 << 31) - 1);
dis[s] = 0;
q.push(make_pair(dis[s],s));
while(!q.empty())
{
int u = q.top().second,v = q.top().first;q.pop();
if(mark[u])continue;
mark[u] = true;
for(int i=Last[u];i;i=edge[i].Next)
{
int k = edge[i].to;
if(mark[k])continue;
if(dis[k] > dis[u] + edge[i].v)
{
dis[k] = dis[u] + edge[i].v;
q.push(make_pair(dis[k],k));
}
}
}
}
void add(int x,int y,int v){edge[++tot].to = y,edge[tot].v = v,edge[tot].Next = Last[x],Last[x] = tot;}
int main()
{
int s;
n = read(),m = read();
for(int i=1;i<=m;i++)
{
x[i] = read(),y[i] = read(),z[i] = read();
add(x[i],y[i],z[i]);
}
dij(1);
long long ans = 0;
for(int i=2;i<=n;i++)ans += dis[i];
for(int i=1;i<=N;i++)edge[i].to = 0,edge[i].v = 0,edge[i].Next = 0,Last[i] = 0;
for(int i=1;i<=m;i++)add(y[i],x[i],z[i]);
dij(1);
for(int i=1;i<=n;i++)ans += dis[i];
printf("%lld",ans);
return 0;
}

评测记录