Codeforces 938D(Dij解带环DP)

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

此做法不是最短路的思路，只是利用dij的松弛来解带环DP
显然这题的转移方程如题所示。

Codeforces Submission

#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;
}