loj#10078. 新年好(最短路)
程序员文章站
2022-07-05 07:59:52
题目: "loj 10078. 新年好" 解析: 亲戚只有五个,可以把它们看成2,3,4,5,6号点,分别跑最短路,记录一下距离,然后DFS一下 这题非常玄学,我开了一个$12 12$的数组,没有离散化,竟然过了,开到$5050 5050$就RE,玄学 代码: cpp include using n ......
题目:
解析:
亲戚只有五个,可以把它们看成2,3,4,5,6号点,分别跑最短路,记录一下距离,然后dfs一下
这题非常玄学,我开了一个\(12*12\)的数组,没有离散化,竟然过了,开到\(5050*5050\)就re,玄学
代码:
#include <bits/stdc++.h> using namespace std; const int n = 1e6 + 10; const int inf = 0x3f3f3f3f; int n, m, num, cnt, ans = inf; int head[n], dis[n], home[n], d[12][12]; bool vis[n], mark[n]; struct node { int v, nx, w; } e[n]; struct edge { int id, dis; bool operator <(const edge &oth) const { return this -> dis > oth.dis; } }; inline void add(int u, int v, int w) { e[++num] = (node) {v, head[u], w}, head[u] = num; } priority_queue<edge>q; void dijkstra(int s) { memset(dis, inf, sizeof dis); memset(vis, 0, sizeof vis); dis[s] = 0; q.push((edge) {s, 0}); while (!q.empty()) { edge d = q.top(); q.pop(); int u = d.id; if (vis[u]) continue; vis[u] = 1; for (int i = head[u]; ~i; i = e[i].nx) { int v = e[i].v; if (dis[v] > dis[u] + e[i].w) q.push((edge) {v, dis[v] = dis[u] + e[i].w}); } } } void dfs(int u, int sum, int cnt) { if (cnt == 5) { ans = min(ans, sum); return; } if (sum > ans) return; for (int i = 2; i <= 6; ++i) { if (!mark[i]) { mark[i] = 1; dfs(i, sum + d[u][i], cnt + 1); mark[i] = 0; } } } int main() { memset(head, -1, sizeof head); cin >> n >> m; for (int i = 1; i <= 5; ++i) cin >> home[i]; for (int i = 1, x, y, z; i <= m; ++i) cin >> x >> y >> z, add(x, y, z), add(y, x, z); dijkstra(1); for (int i = 1; i <= 5; ++i) d[1][i + 1] = d[i + 1][1] = dis[home[i]]; for (int i = 1; i <= 5; ++i) { dijkstra(home[i]); for (int j = i + 1; j <= 5; ++j) d[i + 1][j + 1] = d[j + 1][i + 1] = dis[home[j]]; } mark[1] = 1; dfs(1, 0, 0); cout << ans << endl; }