[pat题解]1003.Emergency

PAT的1003题,题目告诉了一张图,图中有很多城市,给出不同城市之间的通路情况,以及路的距离,每个城市中有一定数量的救援队,现在给定一个源城市和一个目的城市,找一条最短路,是的两城市之间的距离最短,同时保证经过的城市中的救援队总和最大。
所以题目就是个双重条件的最短路问题,第一重条件是距离,第二重条件是救援队的数量,首先保证距离最短,在距离相同的情况下选择救援队数量多的路径。所以可以直接使用dfs搜索得到,加入一些小的剪枝,比如当前距离如果大于已经存在的最小距离,则当前路径无需继续搜索下去了。由于要记录最短路径的条数,所以在搜索到目的节点的时候要注意各个变量的状态更新。

c++代码如下:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <climits>
#include <string.h>

using namespace std;

const int N = 501;

int city[N];
int matrix[N][N];
bool visit[N];

int n, m, st, ed, c1, c2, l;
int sc = 0, mc = 0;
long long minl = LLONG_MAX;

//length:到当前城市(编号cid)的距
//mans:到当前城市能够gather到的team数 
//cid:当前城市编号
void dfs(int length, int mans, int cid)
{
    //找到目的地要更新计数
    if (cid == ed)
    {
        if (length > minl)return;
        if (length < minl)
        {
            sc = 1;
            minl = length;
            mc = mans;
        }
        else
        {
            ++sc;
            if (mc < mans)mc = mans;
        }
        return;
    }

    //剪枝,如果距离大于最小距离,这条路将不用继续走下去了
    if (length > minl)return;
    for (int i = 0; i < n; ++i)
    {
        if (matrix[cid][i] == -1 || visit[i])continue;
        visit[i] = true;
        dfs(length + matrix[cid][i], mans + city[i], i);
        visit[i] = false;
    }
}

int main()
{
    //-1表示i和j表示的城市之间无通路
    memset(matrix, -1, sizeof(matrix));
    memset(visit, 0, sizeof(visit));
    cin >> n >> m >> st >> ed;
    for (int i = 0; i < n; ++i)
    {
        cin >> city[i];
    }
    for (int i = 0; i < m; ++i)
    {
        cin >> c1 >> c2 >> l;
        matrix[c1][c2] = matrix[c2][c1] = l;
    }

    visit[st] = true;
    dfs(0, city[st], st);
    visit[st] = false;

    cout << sc << " " << mc << endl;
    return 0;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[pat题解]1003.Emergency

本文链接地址:http://www.iaccepted.net/algorithm/pat/62.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注