Codeforces 938D(最短路松弛)

Codeforces 938D
题意:给出一张无向带点权带边权图,你需要对于每个点$i$求出$min(2dis_{i,j}+1|j \in E(i, j))$

此做法不是最短路的思路,只是利用dij的松弛
对于每个点,可以利用dij去松弛。先每个点的$dis_i=a_i$,然后每次松弛去找最近的$j$

Codeforces Submission

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
const int MAXN = 2e5 + 5;
ll n, m, en, dis[MAXN], vis[MAXN];
struct edge {
ll v, w;
}ed[MAXN * 2];
struct node {
ll no, w;
bool operator < (const node &b) const {
return w > b.w;
}
};
vector<int> G[MAXN];
void ins(ll u, ll v, ll w) {
en++, ed[en] = (edge){v, w}, G[u].push_back(en);
en++, ed[en] = (edge){u, w}, G[v].push_back(en);
}
void clean() {
ms(vis, 0), en = 0;
}
ll solve() {
clean();
for (ll i = 1; i <= m; i++) {
ll u, v, w;
scanf("%I64d%I64d%I64d", &u, &v, &w);
ins(u, v, w << 1);
}
priority_queue<node > q;
for (ll i = 1; i <= n; i++) scanf("%I64d", &dis[i]), q.push((node){i, dis[i]});
while (!q.empty()) {
node p = q.top(); q.pop();
if (vis[p.no]) continue;
vis[p.no] = true;
for (ll i = 0; i < (ll)G[p.no].size(); i++) {
ll v = ed[G[p.no][i]].v, w = ed[G[p.no][i]].w;
if (dis[p.no] + w < dis[v]) {
dis[v] = dis[p.no] + w;
q.push((node){v, dis[v]});
}
}
}
for (ll i = 1; i <= n; i++) printf("%I64d ", dis[i]);
return 0;
}
int main() {
scanf("%I64d%I64d", &n, &m), solve();
return 0;
}

------ 本文结束 ------