题解 | #I Wanna Go Home#

//土尔逊Torson 编写于2023/07/07
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <climits>
#include <algorithm>

using namespace std;

const int MAXN = 1005;
const int INF = INT_MAX;

struct City_road14001 {
	int to;
	int length;
	City_road14001(int to, int length):to(to),length(length){}
};

struct City14001 {
	int id;
	int distance;
	City14001(int id,int diatance):id(id),distance(distance){}
	bool operator<(City14001 p)const {
		return distance > p.distance;
	}
};

vector<City_road14001> graph14001[MAXN];
int dis14001[3][MAXN];
int leader[MAXN];

void dijkstra14001(int s) {
	int ld = leader[s];

	priority_queue<City14001> q;
	dis14001[ld][s] = 0;
	q.push(City14001(s, dis14001[ld][s]));
	while (!q.empty()) {
		int u = q.top().id;
		q.pop();
		for (int i = 0; i < graph14001[u].size(); ++i) {
			int v = graph14001[u][i].to;
			if (leader[v] != ld) {
				continue;
			}
			int len = graph14001[u][i].length;
			if (dis14001[ld][v] > dis14001[ld][u] + len) {
				dis14001[ld][v] = dis14001[ld][u] + len;
				q.push(City14001(v, dis14001[ld][v]));
			}
		}
	}
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) {
			break;
		}
		int m;
		scanf("%d", &m);

		memset(graph14001, 0, sizeof(graph14001));
		fill(dis14001[1], dis14001[1] + n + 1, INF);
		fill(dis14001[2], dis14001[2] + n + 1, INF);
		while (m--) {
			int from, to, length;
			scanf("%d%d%d", &from, &to, &length);
			graph14001[from].push_back(City_road14001(to, length));
			graph14001[to].push_back(City_road14001(from, length));
		}
		for (int i = 1; i <= n; i++) {
			int ld;
			scanf("%d", &ld);
			leader[i] = ld;
		}

		dijkstra14001(1);
		dijkstra14001(2);

		int answer = INF;
		for (int i = 1; i <= n; ++i) {
			for (auto& City_road14001 : graph14001[i]) {
				int j = City_road14001.to;
				int ld_i = leader[i], ld_j = leader[j];
				if (ld_i != ld_j) {
					int dis_i = dis14001[ld_i][i], dis_j = dis14001[ld_j][j];
					if (dis_i != INF && dis_j != INF) {
						answer = min(answer, dis_i + dis_j + City_road14001.length);
					}
				}
			}
		}
		if (answer == INF) {
			printf("-1\n");
		}
		else {
			printf("%d\n", answer);
		}
	}
	system("pause");
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")