请
柬
请柬
请柬
题目链接：
l
u
o
g
u
1342
luogu\ 1342
luogu 1342
题目背景
在电视时代,没有多少人观看戏剧表演。 Malidinesia 古董喜剧演员意识到这一事实，他们想宣传剧院，尤其是古色古香的喜剧片。
题目
他们已经打印了请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天,邀请人们参与。
这里的公交系统是非常特殊的：共有
n
n
n 个站点和
m
m
m 个线路，所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。
学生每天早上从总部所在的
1
1
1 号站点出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。
输入
输入的第一行是两个整数，代表站点个数
n
n
n 和线路条数
m
m
m。
第
2
2
2 到第
(
m
+
1
)
(m\! +\! 1)
(m+1) 行，每行三个整数
u
,
v
,
w
u, v, w
u,v,w，代表存在一条从
u
u
u 出发到达
v
v
v 的线路，费用为
w
w
w。
输出
输出一行一个整数，表示最小费用。
样例输入
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
样例输出
210
数据范围
对于
100
%
100\%
100% 的数据，保证：
1
≤
n
,
m
≤
1
0
6
1 \leq n, m \leq 10^6
1≤n,m≤106。
1
≤
u
,
v
≤
n
1 \leq u, v \leq n
1≤u,v≤n，
1
≤
w
≤
1
0
9
1 \leq w \leq 10^9
1≤w≤109。 从
1
1
1 出发可以到达所有的站点。
思路
这道题和邮递员送信很像，起点也是都在
1
1
1号点。
不过不同的地方就是数据范围变大了，但是无所谓，这种方法可以过，把数据范围开大一点就可以了。 有一点要注意的是，我们要开
l
o
n
g
l
o
n
g
long\ long
long long。
代码
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std
;
struct node
{
ll to
, next
, x
;
}e1
[10000001], e2
[10000001];
ll n
, m
, p
, x
, y
, z
, ans
, le1
[1000001], le2
[1000001], k
, dis1
[1000001], dis2
[1000001];
bool in
[1000001];
queue
<ll
>q
;
int main() {
memset(dis1
, 0x7f, sizeof(dis1
));
memset(dis2
, 0x7f, sizeof(dis2
));
scanf("%lld %lld", &n
, &m
);
p
= 1;
for (ll i
= 1; i
<= m
; i
++) {
scanf("%lld %lld %lld", &x
, &y
, &z
);
e1
[++k
] = (node
){y
, le1
[x
], z
}; le1
[x
] = k
;
e2
[k
] = (node
){x
, le2
[y
], z
}; le2
[y
] = k
;
}
q
.push(p
);
in
[p
] = 1;
dis1
[p
] = 0;
while (!q
.empty()) {
ll now
= q
.front();
q
.pop();
for (ll i
= le1
[now
]; i
; i
= e1
[i
].next
) {
ll y
= e1
[i
].to
;
if (dis1
[now
] + e1
[i
].x
< dis1
[y
]) {
dis1
[y
] = dis1
[now
] + e1
[i
].x
;
if (!in
[y
]) {
in
[y
] = 1;
q
.push(y
);
}
}
}
in
[now
] = 0;
}
q
.push(p
);
in
[p
] = 1;
dis2
[p
] = 0;
while (!q
.empty()) {
ll now
= q
.front();
q
.pop();
for (ll i
= le2
[now
]; i
; i
= e2
[i
].next
) {
ll y
= e2
[i
].to
;
if (dis2
[now
] + e2
[i
].x
< dis2
[y
]) {
dis2
[y
] = dis2
[now
] + e2
[i
].x
;
if (!in
[y
]) {
in
[y
] = 1;
q
.push(y
);
}
}
}
in
[now
] = 0;
}
for (ll i
= 1; i
<= n
; i
++)
if (i
!= p
)
ans
+= dis1
[i
] + dis2
[i
];
printf("%lld", ans
);
return 0;
}
