神的棋盘

题目描述

在一个棋盘上有许多格子，每个格子上都有 $a_1$ 个红宝石，$a_2$ 个绿宝石，$a_3$ 个黄宝石 $\dots$ $a_n$ 个紫宝石，保证对于不同的格子，由宝石所构成的集合一定不相同。
有一些格子中间存在一条写着 $w$ 的边，若想通过这条边，则每次需要花费 $(\sum\limits_{i = 1}^{n} (a_i - b_i) ^ 2) \times w$。其中 $a_i$ 和 $b_i$ 分别代表边的两端所连接的点的某一种宝石的数量。
注意，这其中总共只有 $m$ 条边。
现在，某人从一个有 $s_1$ 个红宝石，$s_2$ 个绿宝石，$s_3$ 个黄宝石 $\dots$ $s_n$ 个紫宝石的格子上，他想知道到他能走到的所有格子的花费的最小值。特别的，若两个点不联通，那么这两点之间的距离为零，且不能互相到达。

输入格式

第一行输入两个正整数 $n$ 和 $m$。
接下来 $m$ 行，每行输入 $2n + 1$ 个数字，表示点 $u、v$ 的坐标（同时也分别代表宝石数量）以及 $w$
最后一行输入 $n$ 个整数表示起始格。

输出格式

一行一个整数 $\sum dis_i$ 其中 $dis_i$ 表示起始格到点 $i$ 的最小花费。

样例

样例 # 1

样例输入 #1

2 4
1 1 2 3 2
1 1 4 5 1
4 5 6 6 3
1 1 6 6 1
1 1

样例输出 # 1

75

数据范围

测试点	$n$	$m$	$w$
$1 \sim 4$	$=1$	$\le 10 ^ 5$	$\le 10$
$5$	$\ge 2$	$\le 10 ^ 5$	$= 0$
$6 \sim 10$	$\le 5$	$\le 10 ^ 3$	$\le 5$
$11 \sim 20$	$\le 10$	$\le 10 ^ 5$	$\le 10$
对于所有数据，$1 \le n \le 10, 1 \le m \le 10 ^ 5, 1 \le w \le 10, 1 \le a_i \le 100$。

错误代码（25 pts）

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int maxn = 5e5 + 5;
int n, m, tot = 0, cnt = 0;
long long dis[maxn], vis[maxn];
long long to[maxn], val[maxn], nxt[maxn], h[maxn];
struct node {
    long long v, w;
    friend bool operator < (node a, node b) {
        return a.w > b.w;
    }
} tmp;
struct dot {
	long long a[15];
	friend bool operator < (dot a, dot b) {
		for(int i = 1; i <= n; i++) {
            if(a.a[i] != b.a[i]) {
                return a.a[i] < b.a[i]; 
            }
        }
        return 0;
	}
} s;
map< dot, int > Map;
priority_queue<node> q;
long long dist(dot x, dot y, long long w) {
	long long sum = 0;
	for(int i = 1; i <= n; i++) {
		sum += ((x.a[i] - y.a[i]) * (x.a[i] - y.a[i]));
	}
	return sum * w;
}
void add(long long u, long long v, long  long w) {
    tot++;
    to[tot] = v;
    val[tot] = w;
    nxt[tot] = h[u];
    h[u] = tot;
}
void Dijkstra(int s) {
    for(int i = 1; i <= 2 * m; i++) dis[i] = inf, vis[i] = 0;
    dis[s] = 0;
    tmp.v = s, tmp.w = 0;
    q.push(tmp);
    while(!q.empty()) {
        long long u = q.top().v;
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(long long i = h[u]; i; i = nxt[i]) {
            if(dis[to[i]] >  dis[u] + val[i]) {
                dis[to[i]] = dis[u] + val[i];
                tmp.w = dis[to[i]];
                tmp.v = to[i];
                q.push(tmp);
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
    	dot u, v;
		long long w;
    	for(int j = 1; j <= n; j++) {
    		cin >> u.a[j];
		}
		for(int j = 1; j <= n; j++) {
			cin >> v.a[j];
		}
		if(Map[u] == 0) {
			cnt++;
			Map[u] = cnt; 
		}
		if(Map[v] == 0) {
			cnt++;
			Map[v] = cnt;
		}
		cin >> w;
		w = dist(u, v, w);
		add(Map[u], Map[v], w);
	}
    for(int i = 1; i <= n; i++) {
    	cin >> s.a[i];
	}
	if(Map[s] == 0) cnt++, Map[s] = cnt;
    Dijkstra(Map[s]);
    long long ans = 0;
    for(int i = 1; i <= 2 * m; i++) {
        if(dis[i] != inf) {
            ans += dis[i];
        }
    }
    cout << ans << endl;
}

求条，谢谢。
所有关注会在当日内派送完毕。