Vijos - 丛林探险(最短路||DFS)

题目描述

东非大裂谷中有一片神秘的丛林，是全世界探险家的乐园，著名黄皮肤探险家BB一直想去试试。正好我国科学家2005年4月将首次对东非大裂谷进行科考，BB决定随科考队去神秘丛林探险。在出发之前，他搜集了国内外有关神秘丛林探险的资料，并绘制成一张地图：该地图上有若干安全点（包括入口点和出口点），并将这些安全点编号为1、2、…、n；如果一个安全点和另一个安全点有一条路直接相通，则用一条边标示；该图是一个连通图（任意两点间有至少一条路径），地图上每条路的长度和走这条路需要耗费的体力都做了标示。
KK行走速度为1，并知道自己体力为K。他想知道根据自己的体力情况能否成功地穿过丛林。

输入格式

第一行两个整数n（<=5000） m（<=40000），分别表示地图上安全点的个数和边的数目；
第2行至第m+1 行每行4个整数x y c d，x、y表示有直接相联边的两个点的编号，c走这条路需要耗费的体力；d表示边的长度；（其中150<=c,d<=300）
第m+2行两个整数s t，分别表示安全的入口点和出口点的编号；
第m+3行一个整数k，表示BB的体力值；（K<10^9）
同一行上的多个数据用空格隔开。

输出格式

一个整数，如果BB能安全地从如入口穿过丛林到达出口，输出最短时间，否则输出-1

样例输入

4 5
1 2 2 3
1 3 3 5
1 4 7 10
2 4 4 6
3 4 2 6
1 4
5

样例输出

11

限制

各个测试点1s

解题思路

这一题数据比较水，DFS跑一遍就能过，不过还是要剪一下枝。当然最短路也可以过，不过就是要多判断一下体力的问题。具体见代码:
DFS:

#include <cstring>
#include <iostream>
using namespace std;
const int inf = 99999999;
int mins, mint, n, m, k, s, t;
int vis[5005], map[5005][5005], cost[5005][5005];
void DFS(int x, int step, int cot)
{
    vis[x] = 1;
    if (cot > k || step > mins)
        return ;
    if (!(x - t))
    {
        if (step < mins)
        {
            mins = step;
            mint = cot;
        }
        else if (step == mins)
            mint = min(mint, cot);
        return ;
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i] && map[x][i] < inf)
            DFS(i, step + map[x][i], cot + cost[x][i]), vis[i] = 0;
}
int main()
{
    int x, y, c, d;
    while (~scanf("%d%d", &n, &m))
    {
        mins = mint = inf;
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j)    
                    map[i][j] = cost[i][j] = inf;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d%d%d", &x, &y, &c, &d);
            map[x][y] = map[y][x] = min(map[x][y], d);
            cost[x][y] = cost[y][x] = min(cost[x][y], c);
        }
        scanf("%d%d%d", &s, &t, &k);
        DFS(s, 0, 0);
        if (mint <= k)
            printf("%d\n", mins);
        else printf("-1\n");
    }
    return 0;
}

Dijkstra:

#include <iostream>
using namespace std;
int n, m, s, t, maxn;
const int inf = 99999999;
int dit[5005], dis[5005], vis[5005], map[5005][5005], cost[5005][5005];
void Dijkstra(int s)
{
    int minn, k;
    for (int i = 1; i <= n; i++)
    {
        vis[i] = 0;
        dit[i] = dis[i] = inf;
    }
    dit[s] = dis[s] = 0;
    for (int i = 0; i < n; i++)
    {
        k = s;
        minn = inf;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && minn > dis[j])
                minn = dis[k = j];
        vis[k] = 1;
        for (int j = 1; j <= n; j++)
            if (dit[k] + cost[k][j] <= maxn)
                if (!vis[j] && map[k][j] < inf)
                    if (dis[j] > dis[k] + map[k][j])
                        dis[j] = dis[k] + map[k][j], dit[j] = dit[k] + cost[k][j];
                    else if (dis[j] == dis[k] + map[k][j])
                        dit[j] = min(dit[j], dit[k] + cost[k][j]);
    }
}
int main()
{
    int x, y, c, d;
    while (~scanf("%d%d", &n, &m))
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (i != j)    
                    map[i][j] = cost[i][j] = inf;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d%d%d", &x, &y, &c, &d);
            map[x][y] = map[y][x] = min(map[x][y], d);
            cost[x][y] = cost[y][x] = min(cost[x][y], c);
        }
        scanf("%d%d%d", &s, &t, &maxn);
        Dijkstra(s);
        if (dit[t] <= maxn)
            printf("%d\n", dis[t]);
        else printf("-1\n");
    }
    return 0;
}