最短路变形 poj3615&

时间：2021-03-11 17:45:41

问题：

牛要跨过一些障碍，希望以最小的体力跨过障碍，并且对于一条路径，只在乎其中最高的障碍。

输入N代表站点数，标记为1—N，输入M代表路径数，从站点S到E之间需要跨过高度为H的障碍。

输入T代表牛要完成的任务数。对于每个任务，输入A，B，输出一条从站点A到B的路径，使需要跨过的最高障碍为最低。

代码：（Floyd

/*******************************************

Problem: 3615		User:

Memory: 960K		Time: 688MS

Language: G++		Result: Accepted

********************************************/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 305;

int mp[N][N];

int dis[N], vis[N];

void floyd(int n)

{

    int i, j, k;

    for (k = 1; k <= n; ++k)

        for (i = 1; i <= n; ++i)

            for (j = 1; j <= n; ++j)

            if (mp[i][j] > max(mp[i][k] , mp[k][j]))

                mp[i][j] = max(mp[i][k], mp[k][j]);

}

int main()

{

    int n, m, t;

    while (scanf("%d%d%d", &n, &m, &t) != EOF) {

        int i, j;

        int a, b, h;

        for (i = 1; i <= n; ++i)

            for (j = 1; j <= n; ++j)

                mp[i][j] = INF;

        for (i = 0; i < m; ++i) {

            scanf("%d%d%d", &a, &b, &h);

            mp[a][b] = h;

        }

        floyd(n);

        for (i = 0; i < t; ++i) {

            scanf("%d%d", &a, &b);

            printf("%d\n", mp[a][b] == INF ? -1 : mp[a][b]);

        }

    }

    return 0;

}

　　

poj2263

和上题相似，求两点之间最小值最大的路径

代码：（dijkstra

/******************************************

Problem: 2263		User:

Memory: 812K		Time: 125MS

Language: G++		Result: Accepted

*******************************************/

#include <iostream>

#include <cstring>

#include <string>

#include <map>

#include <algorithm>

#include <cstdio>

using namespace std;

const int N = 205;

const int INF = 0x3f3f3f3f;

int mp[N][N];

int vis[N], dis[N];

map<string, int>my_map;

int dijkstra(int n, int s, int e)

{

    int i, j;

    memset(vis, 0, sizeof(vis));

    for (i = 1; i <= n; ++i)

        dis[i] = mp[s][i];

    vis[s] = 1;

    for (i = 0; i < n; ++i) {

        int max_dis = 0;

        int max_x = 1;

        for (j = 1; j <= n; ++j) {

            if (!vis[j] && dis[j] > max_dis) {

                max_dis = dis[j];

                max_x = j;

            }

        }

        if (max_x == e) return max_dis;

        vis[max_x] = 1;

        for (j = 1; j <= n; ++j) {

            if (!vis[j] && dis[j] < min(dis[max_x], mp[j][max_x]))

                dis[j] = min(dis[max_x], mp[j][max_x]);

        }

    }

    return 0;

}

int main()

{

    int n, m;

    int times = 1;

    while (scanf("%d%d", &n, &m) != EOF) {

        if (n == 0 && m == 0) break;

        int i, j;

        my_map.clear();

        int cnt = 1;

        string stra, strb;

        int x, y;

        int weight;

        for (i = 1; i <= n; ++i)

            for (j = 1; j <= n; ++j)

                mp[i][j] = 0;

        for (i = 0; i < m; ++i) {

            cin >> stra >> strb >> weight;

            if (my_map[stra] == 0)  my_map[stra] = cnt++;

            if (my_map[strb] == 0)  my_map[strb] = cnt++;

            x = my_map[stra];

            y = my_map[strb];

            if (mp[x][y] < weight)

                mp[y][x] = mp[x][y] = weight;

        }

        cin >> stra >> strb;

        x = my_map[stra];

        y = my_map[strb];

        printf("Scenario #%d\n%d tons\n\n", times++, dijkstra(n, x, y));

    }

    return 0;

}

　　

相关文章