雙調路徑-有解無憂

雙調路徑

思路：我們可以容易想到，通過不同的邊到達某個點的時間和金錢是不一樣的，這是難點，我們發現點數n = 100，權值t,c = 100，如果我們分別維護時間權值為x時，到達該城市的最少金錢是多少，即d[城市][時間] = 金錢，因為 n = 100, t,c = 100，說明我們需要維護 n*t 個點的值，則邊數為 n * t * m = 3e6，我們可以用spfa解決，

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>

using namespace std;

#define ll long long
#define pb push_back
#define fi first
#define se second

const int INF = 2e4;

struct node {
    int v, c, t;
};

void SPFA(int n, int S, int T, vector<vector<node> >& E) {
    int _size = n * 100;
    vector<vector<bool> > vis(n + 1, vector<bool>(_size + 100, 0));
    vector<vector<int> > d(n + 1, vector<int>(_size + 100, INF));
    queue<pair<int, int> > que;
    vis[S][0] = true;
    d[S][0] = 0;
    que.push(make_pair(S, 0));

    while (!que.empty()) {
        int u = que.front().fi;
        int w = que.front().se;
        que.pop();
        vis[u][w] = false;
        for (auto e : E[u]) {
            if (w + e.t > n * 100)
                continue;  //最多 n * 100 的時間消耗，沒有限制，則d[x][∞]會一直更新
            if (d[e.v][w + e.t] > d[u][w] + e.c) {
                d[e.v][w + e.t] = d[u][w] + e.c;
                if (!vis[e.v][w + e.t]) {
                    vis[e.v][w + e.t] = true;
                    que.push(make_pair(e.v, w + e.t));
                }
            }
        }
    }
    int ans = 0;
    int Min = INF;
    for (int i = 0; i <= n * 100; ++i) {
        if (d[T][i] < Min) {
            ++ans;
            Min = d[T][i];
        }
    }
    printf("%d\n", ans);
    // cout << "this" << endl;
}

void solve() {
    int n, m, S, T;
    scanf("%d%d%d%d", &n, &m, &S, &T);
    vector<vector<node> > E(n + 1);
    int u, v, c, t;
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d%d", &u, &v, &c, &t);
        E[u].pb({ v, c, t });
        E[v].pb({ u, c, t });
    }

    SPFA(n, S, T, E);
}

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0); cout.tie(0);
    // freopen("C:\\Users\\admin\\Desktop\\input.txt", "r", stdin);
    // freopen("C:\\Users\\admin\\Desktop\\output.txt", "w", stdout);
    solve();
    // cout << "not error" << endl;
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/49742.html

標籤：其他

上一篇：二叉樹的遍歷及常用演算法

下一篇：ICPC 2019-2020 North-Western Russia Regional Contest E. Equidistant（分層）