PAT A1003 Emergency(25)

题意

• 给定图（城市，路），给定边权（路程），点权（救援队数目），求两点间最短路条数（边权和最小），并求其中点权和的最大值。

注意

单词

1. scatter 分散

代码

#include <iostream>
#include <climits>

using namespace std;

const int MAX = 500;
int n, m;
int s, t;
int v_wei[MAX];     //点权
int e_wei[MAX][MAX];//边权

int road[MAX];      //最短路条数（至起点）（*）
int v_max[MAX];     //最短路的点权最大（至起点）（*）
int e_min[MAX];     //边权最小（最短路长度）（至起点）
bool S[MAX];        //S集

void Dijkstra(int s0)
{
	fill(S, S + n, false);
	fill(e_min, e_min + n, INT_MAX);
	
	v_max[s0] = v_wei[s0];
	e_min[s0] = 0;    / s0作为起点还未加入
	road[s0] = 1;

	for (int i = 0; i < n; i++)
	{
		int min = INT_MAX;
		int u;
		for (int j = 0; j < n; j++)
		{
			if (!S[j] && e_min[j] < min)
			{
				min = e_min[j];
				u = j;
			}
		}
		S[u] = true;                               //
		for (int k = 0; k < n; k++)
		{
			if (!S[k] && e_wei[u][k] != INT_MAX)        /
			{
				if (e_min[u] + e_wei[u][k] < e_min[k])
				{
					road[k] = road[u];                ///
					e_min[k] = e_min[u] + e_wei[u][k];
					v_max[k] = v_max[u] + v_wei[k];
				}
				else if (e_min[u] + e_wei[u][k] == e_min[k])
				{
					road[k] += road[u];            // 这里road[k]的旧值必定被以前轮次的 u 赋过值，不然else if条件不可能成立，因为e_min初始化均为INT_MAX
					if (v_max[k] < v_max[u] + v_wei[k])    
						v_max[k] = v_max[u] + v_wei[k];
				}
			}
		}
	}
}

int main()
{
	scanf_s("%d%d%d%d", &n, &m, &s, &t);
	for (int i = 0; i < n; i++)
		scanf_s("%d", &v_wei[i]);

	fill(e_wei[0], e_wei[0] + MAX*MAX, INT_MAX);     [0] MAX*MAX!!!!!!!!!!!!!!

	int v1, v2;
	for (int i = 0; i < m; i++)
	{
		scanf_s("%d%d",&v1,&v2);
		scanf_s("%d", &e_wei[v1][v2]);
		e_wei[v2][v1] = e_wei[v1][v2];
	}
	
	Dijkstra(s);
	printf("%d %d", road[t], v_max[t]);

    return 0;
}