图论 - PAT甲级 1003 Emergency C++

PAT甲级 1003 Emergency C++

Input Specification:

Output Specification:

Sample Input:

Sample Output:

由于初学图论此题参考了柳神的代码:

https://blog.csdn.net/liuchuo/article/details/52300668

这个小姐姐代码写的很好,大家可以多去逛逛她的博客哦!:

https://www.liuchuo.net/

题目大意:

分析

#include <iostream>

#include <algorithm>

using namespace std;

int n, m, c1, c2;

int e[510][510], weight[510], dis[510], num[510], w[510];

//num表示不同最短路径的数量 w表示可以到达各个点的最大队伍数量

bool visit[510];

const int inf = 99999999;

int main() {

	scanf("%d%d%d%d", &n, &m, &c1, &c2);

	for (int i = 0; i < n; i++)

		scanf("%d", &weight[i]);

	//初始化操作

	fill(e[0], e[0] + 510 * 510, inf);

	fill(dis, dis + 510, inf);

	//读入边

	int a, b, c;

	for (int i = 0; i < m; i++) {

		scanf("%d%d%d", &a, &b, &c);

		e[a][b] = e[b][a] = c;

	}

	//初始化源点

	dis[c1] = 0;

	w[c1] = weight[c1]; //初始化源点到自己的队伍数

	num[c1] = 1;        //初始化源点到自己的路径数量

    //Dijkstra算法核心

	for (int i = 0; i < n; i++)

	{

		int u = -1, minn = inf;

		//找到当前距离源点最近的点

		for (int j = 0; j < n; j++)

		{

			if (visit[j] == false && dis[j] < minn)

			{

				u = j;

				minn = dis[j];

			}

		}

		if (u == -1) break; //如果以上的点都被遍历完就停止

		visit[u] = true;

		//寻找经过该中转点可以直接到达的点

		for (int v = 0; v < n; v++)

		{

			if (visit[v] == false && e[u][v] != inf)

			{

				if (dis[u] + e[u][v] < dis[v]) //如果此时是最短路径

				{

					dis[v] = dis[u] + e[u][v]; //更新最短路径长度

					num[v] = num[u];

					w[v] = w[u] + weight[v];   //更新最短路路径的最大队伍数量

				}

				else if (dis[u] + e[u][v] == dis[v])

				{

					num[v] = num[v] + num[u];

					if (w[u] + weight[v] > w[v])

						w[v] = w[u] + weight[v];

				}

			}

		}

	}

	printf("%d %d", num[c2], w[c2]);

	return 0;

}