1003 Emergency

1003 Emergency（25 分）

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:

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between

Sample Input:

Sample Output:

2 4

//本题可以归结为：求图的最小路径及最小路径的数量
//要求输出：最小路径的数量，能聚集救援队的最大数量（即最短路径中点对应值的和的最大值）

#include<stdio.h>
#include<iostream>

using namespace std; 

int flag[501] = {0};//标志值，确定是否为最短路径，0不是，1是
int dist[501];//存放结点到出发点的最短路径长度权
int pathcount[501];//存放结点到出发点最短路径的数量
int amount[501];// 存放结点到出发点最短路径中权重的最小值

int map[501][501];//记录两端点长度，实际中只用0~N即可

const int INF = 0x7fffffff;//无穷大

int main()
{
    /*step1：输入参数*/

    int N;//城市数量，点
    int M;//道路数量，边
    int C1;//待救援城市，出发点
    int C2;//当时所在城市，目的地

    cin >> N;
    cin >> M;
    cin >> C1;
    cin >> C2;

    //输入城市0~n-1 中救援队的数量，即点对应的权重
    int weight [501];
    for(int i = 0;i < N;i++)
    {
        cin >> weight[i];
    }

    //初始化map和dist
    for(int i = 0;i < N;i++)
    {
        for(int j = 0;j < N;j++)
        {
            if (i == j)
            {
                map[i][j] = 0;
            }
            else
            {
                map[i][j] = INF;
            }
        }
    }

    for(int i = 0;i < N;i++)
    {
        dist[i] = map[C1][i];
    }

    int c1,c2,L;//输入M边的两端点和长度
    for(int i = 0;i < M;i++)
    {
        cin >> c1;
        cin >> c2;
        cin >> L;
        map[c1][c2] = L;
        map[c2][c1] = L;
    }

    /*step2：Dijkstar算法求最短路径*/

    //初始化    
    //flag[C1] = 1;
    dist[C1] = 0;
    pathcount[C1] = 1;
    amount[C1] = weight[C1];
    int min;//辅助变量，最短路径
    int k = 0;//辅助变量

    //遍历，每次确定一个结点最短路径
    for(int j = 0;j < N;j++)
    {
        min  = INF; //主义
        //寻找当前最短路径（第一个结点，相邻的）
        for(int i = 0;i < N;i++)
        {
            if(flag[i] == 0 && dist[i] < min)
            {
                min = dist[i];
                k = i;
            }
        }
        flag[k] = 1;

        //往后面继续寻找
        for(int i = 0;i < N;i++)
        {
            if(flag[i] == 0 && map[k][i] != INF)//遍历除出发点和第一个点之外的点
            {
                if(dist[i] > dist[k] + map[k][i])
                {
                    dist[i] = dist[k] + map[k][i];
                    amount[i] = amount[k] + weight[i];
                    pathcount[i] = pathcount[k];
                }
                else if(dist[i] == dist[k] + map[k][i])
                {
                    if(amount[i] < amount[k] + weight[i]) 
                    {
                        amount[i] = amount[k] + weight[i];
                    }
                    pathcount[i] += pathcount[k];
                }
            }
        }

        if(k == C2)
        {
            break;
        }
    }
    

    /*step3:输出结果*/
    cout << pathcount[C2] << " " << amount[C2] <<endl;

    return 0;
}