通往奥格瑞玛的道路

二分一下最大费用,找出最小值,每次都跑一遍SPFA判断一下以这个为最大费用能不能跑到终点

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;

const int N = 10010, M = 50050, INF = 0x3f3f3f3f;

int n, m, s;
LL dis[N];
int res[N], cot[N];
bool st[N];
int e[M << 1], w[M << 1], ne[M << 1], h[N], idx;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool check(int x)
{
    if (cot[1] > x) return false;
    // 这里要先判断一下起点的费用是不是超过了x,不然最后一个点会被卡
    memset(dis, 0x3f, sizeof dis);
    memset(st, 0, sizeof st);

    queue<int> q;
    q.push(1);
    st[1] = true;
    dis[1] = 0;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i], v = w[i];

            if (cot[j] > x) continue;

            if (dis[j] > dis[t] + v)
            {
                dis[j] = dis[t] + v;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dis[n] <= s;
}

int main()
{
    scanf ("%d %d %d", &n, &m, &s);
    // 这里要单独开一个数组然后把它搞成单调的,这样才能二分
    for (int i = 1; i <= n; i ++) scanf ("%d", &cot[i]), res[i] = cot[i];

    sort(res + 1, res + n + 1);
    memset(h, -1, sizeof h);
    while (m --)
    {
        int a, b, c;
        scanf ("%d %d %d", &a, &b, &c);
        if (a != b)
        {
            add(a, b, c);
            add(b, a, c);
        }
    }

    if (!check(INF)) // 如果最大费用为INF都到不了,说明怎么样都到不了终点
    {
        puts("AFK");
        return 0;
    }

    int l = 1, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(res[mid])) r = mid;
        else l = mid + 1;
    }

    printf ("%d", res[l]);
    return 0;
}

最小花费

$Dijkstra$适用情景:

$1$. $0<=$边权, 求路径边权之和最小值 (保证更新过程中$dis[i]$越来越大)

$2.$ $0 <=$ 边权 $<= 1$, 求路径边权之积最大值 (保证更新过程中$dis[i]$越来越小)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2020;

int n, m;
double dis[N], g[N][N];
int s, t;
bool st[N];

void Dijkstra()
{
    // 此时就不用初始化为正无穷了, 因为不存在的边的边权为0, 一乘dis[i]就为最小值0
    dis[s] = 1; // 乘积的话要初始化为 1

    for (int i = 1; i <= n; i ++)
    {
        int t = -1;
        for (int j = 1; j <= n; j ++)
            if (!st[j] && (t == -1 || dis[t] < dis[j]))
                t = j;
        st[t] = true;

        for (int j = 1; j <= n; j ++) dis[j] = max(dis[j], dis[t] * g[t][j]);
    }
}

int main()
{
    cin >> n >> m;

    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = max(g[a][b], (100.0 - c) / 100);
    }

    cin >> s >> t;

    Dijkstra();

    printf ("%.8lf", 100.0 / dis[t]);
    return 0;
}

最优乘车

思路: 对于每一条路线上的点, 往位于这条线上这个点后面的所有点都建一条边, 然后求从1到N的最短路即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>

using namespace std;

const int N = 550, INF = 0x3f3f3f3f;

int m, n;
bool g[N][N]; // 可以用邻接矩阵判断两个车站是不是相通
int dis[N], q[N];
int stop[N];

void bfs()
{
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;

    int hh = 0, tt = 1;
    q[0] = 1;

    while (hh != tt)
    {
        int t = q[hh ++];
        if (hh == N) hh = 0;

        for (int i = 1; i <= n; i ++)
            if (g[t][i] && dis[i] > dis[t] + 1)
            {
                dis[i] = dis[t] + 1;
                q[tt ++] = i;
                if (tt == N) tt = 0;
            }
    }
}

int main()
{
    cin >> m >> n;

    string line;
    getline(cin, line); // 把换行符读掉
    while (m --)
    {
        getline(cin, line);
        stringstream ssin(line); // 把line中的内容赋给ssin
        int cnt = 0, p;
        while (ssin >> p) stop[cnt ++] = p; // 再把ssin中的内容以int类型的值赋给p
        for (int i = 0; i < cnt; i ++)
            for (int j = i + 1; j < cnt; j ++)
                g[stop[i]][stop[j]] = true;
    }

    bfs();

    if (dis[n] == INF) puts("NO");
    else printf ("%d", dis[n] - 1); // 因为初始点就在一条线上, 所以第一次不用换乘
    return 0;
}