1003 Emergency (25分)

1. 题目

2. 样例输入

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

3. 样例输出

2 4

4. 思路

第一次做的时候还图样图森破
第一次遇见图的时候是完全懵逼的
不过现在回过头来看图的题还是非常简单的…
说起图想起一个技巧就是#define maxn 1000000www
这题需要用迪杰斯特拉算法将题目中的最短路径算出,然后在路径长度的情况下比较他们能获得的人力资源,最多的就是最优解

5. AC代码

#include <iostream>
#include <algorithm>
using namespace std;
#define Maxn 505
#define inf 99999
int City[Maxn][Maxn];
int manpower[Maxn];
int dist[Maxn];
bool vis[Maxn]{ false };
int W[Maxn];
int num[Maxn];
int N, M, start, result;

int main() {
	cin >> N >> M >> start >> result;
	for (int n = 0; n < N; n++) {
		cin >> manpower[n];
	}
	fill(City[0],City[0] + Maxn*Maxn, inf);
	fill(dist, dist + Maxn, inf);
	for (int n = 0; n < M; n++) {
		int a, b; cin >> a >> b;
		cin >> City[a][b];
		City[b][a] = City[a][b];
	}
	dist[start] = 0;
	W[start] = manpower[start];
	num[start] = 1;
	for (int n = 0; n < N; n++) {
		int min = inf, u = -1;
		for (int m = 0; m < N; m++) {
			if (vis[m] == false && dist[m] < min) {
				min = dist[m];
				u = m;
			}
		}
		if (u == -1)break;
		vis[u] = true;
		for (int i = 0; i < N; i++) {
			if (vis[i] == false && City[u][i] != inf) {
				if (dist[u] + City[u][i] < dist[i]) {
					dist[i] = dist[u] + City[u][i];
					num[i] = num[u];
					W[i] = W[u]+manpower[i];
				}
				else if (dist[u] + City[u][i] == dist[i]) {
					num[i] = num[i] + num[u];
					if (W[u] + manpower[i] > W[i]) {
						W[i] = W[u] + manpower[i];
					}
				}
			}
		}
	}
	cout << num[result] << " " << W[result];
	return 0;
}