|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
#pragma region SPFA算法模板
|
|
|
// 最短路径——SPFA算法
|
|
|
|
|
|
// 最大值
|
|
|
// https://blog.csdn.net/jiange_zh/article/details/50198097
|
|
|
/**
|
|
|
如果我们想要将某个数组清零，我们通常会使用memset(a,0,sizeof(a))，方便又高效，但是当我们想将某个数组全部赋值为无穷大时，
|
|
|
就不能使用memset函数而得自己写循环了，因为memset是按字节操作的，它能够对数组清零是因为0的每个字节都是0（一般我们只有赋值为-1
|
|
|
和0的时候才使用它）。现在好了，如果我们将无穷大设为0x3f3f3f3f，那么奇迹就发生了，0x3f3f3f3f的每个字节都是0x3f！所以要把一段
|
|
|
内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。所以在通常的场合下，0x3f3f3f3f真的是一个非常棒的选择！
|
|
|
*/
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
|
|
|
// https://www.cnblogs.com/xzxl/p/7246918.html
|
|
|
int matrix[100][100]; //邻接矩阵
|
|
|
bool visited[100]; //标记数组
|
|
|
int dist[100]; //源点到顶点i的最短距离
|
|
|
int path[100]; //记录最短路的路径
|
|
|
int enqueue_num[100]; //记录入队次数
|
|
|
int vertex_num; //顶点数
|
|
|
int edge_num; //边数
|
|
|
int source; //源点
|
|
|
|
|
|
bool SPFA() {
|
|
|
memset(visited, 0, sizeof(visited));
|
|
|
memset(enqueue_num, 0, sizeof(enqueue_num));
|
|
|
for (int i = 1; i <= vertex_num; i++) {
|
|
|
dist[i] = INF;
|
|
|
path[i] = source;
|
|
|
}
|
|
|
queue<int> Q;
|
|
|
Q.push(source);
|
|
|
dist[source] = 0;
|
|
|
visited[source] = 1;
|
|
|
enqueue_num[source]++;
|
|
|
while (!Q.empty()) {
|
|
|
int u = Q.front();
|
|
|
Q.pop();
|
|
|
visited[u] = 0;
|
|
|
for (int v = 1; v <= vertex_num; v++) {
|
|
|
if (matrix[u][v] != INF) //u与v直接邻接
|
|
|
{
|
|
|
if (dist[u] + matrix[u][v] < dist[v]) {
|
|
|
dist[v] = dist[u] + matrix[u][v];
|
|
|
path[v] = u;
|
|
|
if (!visited[v]) {
|
|
|
Q.push(v);
|
|
|
enqueue_num[v]++;
|
|
|
if (enqueue_num[v] >= vertex_num)
|
|
|
return false;
|
|
|
visited[v] = 1;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
void Print() {
|
|
|
for (int i = 1; i <= vertex_num; i++) {
|
|
|
if (i != source) {
|
|
|
int p = i;
|
|
|
stack<int> s;
|
|
|
cout << "顶点 " << source << " 到顶点 " << p << " 的最短路径是： ";
|
|
|
while (source != p) //路径顺序是逆向的，所以先保存到栈
|
|
|
{
|
|
|
s.push(p);
|
|
|
p = path[p];
|
|
|
}
|
|
|
cout << source;
|
|
|
while (!s.empty()) //依次从栈中取出的才是正序路径
|
|
|
{
|
|
|
cout << "--" << s.top();
|
|
|
s.pop();
|
|
|
}
|
|
|
cout << " 最短路径长度是：" << dist[i] << endl;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
#pragma endregion SPFA算法模板
|
|
|
|
|
|
int main() {
|
|
|
//录入参数文件
|
|
|
freopen("../1411.txt", "r", stdin);
|
|
|
|
|
|
int n;
|
|
|
// 奶牛数,牧场数,牧场间道路数
|
|
|
cin >> n >> vertex_num >> edge_num;
|
|
|
|
|
|
//每个牧场的奶牛数量
|
|
|
vector<int> naiNiuCountArr(vertex_num + 1); //这个容器开始时有 vertex_num + 1 个元素，它们的默认初始值都为 0。
|
|
|
for (int i = 1; i <= n; ++i) {
|
|
|
int d;
|
|
|
cin >> d;
|
|
|
naiNiuCountArr[d]++;
|
|
|
}
|
|
|
|
|
|
//初始为两个节点之间为无穷大
|
|
|
for (int i = 1; i <= vertex_num; i++)
|
|
|
for (int j = 1; j <= vertex_num; j++)
|
|
|
matrix[i][j] = INF; //初始化matrix数组
|
|
|
|
|
|
//读入edge_num条边的信息
|
|
|
for (int i = 1; i <= edge_num; ++i) {
|
|
|
int a, b, c;
|
|
|
cin >> a >> b >> c;
|
|
|
matrix[a][b] = c; //双向，表示是无向图
|
|
|
matrix[b][a] = c; //双向，表示是无向图
|
|
|
}
|
|
|
|
|
|
//遍历每一个顶点,假设将糖放在这个顶点上
|
|
|
int minPath = INF;
|
|
|
int point_vertex_num;
|
|
|
for (int i = 1; i <= vertex_num; ++i) {
|
|
|
//每个顶点都算一次到各个其它顶点的距离
|
|
|
source = i;
|
|
|
SPFA();
|
|
|
//Print();
|
|
|
//假设从source节点出发的话，那么需要所有奶牛共同加在一起走的最小路径和
|
|
|
int allPath = 0;
|
|
|
for (int j = 1; j <= vertex_num; j++) {
|
|
|
allPath += dist[j] * naiNiuCountArr[j];
|
|
|
}
|
|
|
//挑出最少的那个节点路径和
|
|
|
if (minPath > allPath) {
|
|
|
minPath = allPath;
|
|
|
//记录是哪个节点时发生了这个变化
|
|
|
point_vertex_num = source;
|
|
|
}
|
|
|
}
|
|
|
// cout << minPath << " " << point_vertex_num << endl;
|
|
|
cout << minPath << endl;
|
|
|
//关闭文件
|
|
|
fclose(stdin);
|
|
|
return 0;
|
|
|
}
|
