1003 Emergency 紧急事件

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

作为一名城市的紧急救援队队长，你被赋予了一张特殊的国家地图。地图显示了几个分散的城市，这些城市之间由一些道路相连。地图上标注了每个城市的救援队数量以及任意两个城市之间道路的长度。当其他城市发出紧急呼叫时，你的工作是尽快带领你的队员前往现场，并在途中尽可能地召集更多的援助。

Input Specification:

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.

每个输入文件包含一个测试用例。对于每个测试用例，

第一行包含4个正整数：N (≤500) - 城市数量（城市编号从0到N−1），M- 道路数量，C1和C2 - 当前所在城市和必须救援的城市。

下一行包含N个整数，其中第i个整数是第i个城市的救援队数量。

然后是M行，每行描述一条道路，其中包含三个整数c1，c2和L，分别是连接一条道路的城市对和该道路的长度。

保证存在至少一条从C1到C2的路径。

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

对于每个测试用例，一行输出两个数字：C1和C2之间不同的最短路径数和最多可能聚集的救援队数量。

每行中所有数字之间必须恰好有一个空格，行末不能有多余空格。

Sample Input:

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

Sample Output:

2 4

解释：最短路径有两条，即【C1-C3】- aid 2，【C1-C2-C3】 - aid 4

我们选择最短的aid累计最多的。

我的思路

#include<bits/stdc++.h>
using namespace std;
//C1到C2途径累加的aid最多 
int main(){
	//第一行包含4个正整数：
	//N (≤500) - 城市数量（城市编号从0到N1），
	//M- 道路数量，
	//C1和C2 - 当前所在城市和必须救援的城市。
	int N,M,C1,C2;
	cin>>N>>M>>C1>>C2;
	//下一行包含N个整数，其中第i个整数是第i个城市的救援队数量。
	int aid[N];
	for(int i=0;i<N;i++){
		cin>>aid[i];
	}
	//使用二维数组存储图 
	int path[N][N];
	//然后是M行，每行描述一条道路，
	//其中包含三个整数c1，c2和L，分别是连接一条道路的城市对和该道路的长度。
	for(int i=0;i<M;i++){
		int c1,c2,l;
		cin>>c1>>c2>>l;
		path[c1][c2]=l;
	}
	//使用并查集进行最短路径的迪杰斯特拉算法 
	//fartherpath[i][0]：父节点
	//fartherpath[i][1]：累计路径
	//fartherpath[i][2]：累计aid
    int fartherpath[N][3];
	queue<int> que;
	que.push(C1);
    ...
}

加上题目翻译耗时半个小时左右，有点慢，实战必写不完，看看题解怎么写的。

Solution

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, c1, c2;
//dis C1到达各结点累计路程
//num 到达指定结点最短路径数
//w 累计aid表 
int path[510][510], aid[510], dis[510], num[510], w[510];
//visit访问标志（已确定最短路径的点）
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", &aid[i]);
    
	//道路信息存储在path图中，且无道路为无穷大
	fill(path[0], path[0] + 510 * 510, inf);
    int a, b, c;
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        path[a][b] = path[b][a] = c;
    }
    //******************************************
    //迪杰斯特拉算法
    
    //step1初始化
    //1.dis C1到达各结点累计路程
    //都不可达
    fill(dis, dis + 510, inf);
    //源点可达，置为0
    dis[c1] = 0;
    //2.w 累计救援数
    //源点救援数为本身救援数
    w[c1] = aid[c1];
    //3.num 到达指定结点最短路径数
    //到达源点就1条路
    num[c1] = 1;
    
    //step2遍历图 
    //每次循环目的：
    //1.纳新-接纳一个最小路径外的最近结点
    //2.传销-让新成员发展下线
    for(int i = 0; i < n; i++) {
    	//1.纳新
        //要求结点未在最短路径内且距离C1最近
        //u 拟纳新的结点下标
        //minn 该结点距离C1的距离
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++) {
        	//结点未在最短路径内且距离C1最近
            if(visit[j] == false && dis[j] < minn) {
                u = j;
                minn = dis[j];
            }
        }
        //如果无新可纳，就结束吧
        if(u == -1) break;
        //纳新后得发徽章
        visit[u] = true;
        
        //2.传销
        //让新成员发展下线
        for(int v = 0; v < n; v++) {
        	//结点未在最短路径内且该结点与新成员之间存在通路
            if(visit[v] == false && path[u][v] != inf) {
            	//如果 新成员到达该点的距离 比 之前的距离 短
                //1.更新累计距离
                //2.更新到达该结点最短路径数
                //3.更新累计救援数(直接累加)
                if(dis[u] + path[u][v] < dis[v]) {
                    dis[v] = dis[u] + path[u][v];
                    num[v] = num[u];
                    w[v] = w[u] + aid[v];
                }
                //如果 新成员到达该点的距离 与 之前的距离 相等
                //1.更新到达该结点最短路径数(两条支路累加)
                //3.更新累计救援数(需要比较两条支路)
				else if(dis[u] + path[u][v] == dis[v]) {
                    num[v] = num[v] + num[u];
                    if(w[u] + aid[v] > w[v])
                        w[v] = w[u] + aid[v];
                }
            }
        }
    }
    //******************************************
    //输出
    printf("%d %d", num[c2], w[c2]);
    return 0;
}