题目链接

链接

题目大意

有一张图，找一个点出发，使得到达最远的点代价最小，输出k到个点的最小代价和最大价值

题解

题解1

先用floyd跑一遍算出最远端点代价最小的点。然后再用dijkstra算出到k个点的最小代价和最大价值

代码

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define int long long
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2100;
struct edge {
    int to, v, w;
};
struct node {
    int x, v, w;
    bool operator<(const node& w) const
    {
        if (v == w.v)
            return this->w < w.w;
        return v > w.v;
    }
};
vector<edge> a[N];
int dist[N], val[N], vis[N], d[N][N];
int n, m, st;

void floyd()
{
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    int sum = INF;
    for (int i = 1; i <= n; i++) {
        int res = 0;
        for (int j = 1; j <= n; j++) {
            // if (d[i][j] != INF) {
            res = max(res, d[i][j]);
            // }
        }
        if (res < sum) {
            sum = res;
            st = i;
        }
    }
}

int fa[N];
void dfs(int u)
{
    if (fa[u] == -1) {
        return;
    }
    dfs(fa[u]);
    cout << "->" << u;
}

void dijkstra(int u)
{
    for (int i = 1; i <= n; i++) {
        fa[i] = -1;
        dist[i] = INF;
    }

    dist[u] = 0, val[u] = 0;
    priority_queue<node> q;
    q.push({ u, 0, 0 });
    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.x;
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto i : a[u]) {
            int v = i.to;
            if (dist[v] > dist[u] + i.v) {
                fa[v] = u;
                dist[v] = dist[u] + i.v;
                val[v] = val[u] + i.w;
                q.push({ v, dist[v], val[v] });
            } else if (dist[v] == dist[u] + i.v && val[v] < val[u] + i.w) {
                fa[v] = u;
                val[v] = val[u] + i.w;
                q.push({v, dist[v], val[v] });
            }
        }
    }
}

void solve()
{
    memset(d, 0x3f, sizeof d);
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int x, y, w1, w2;
        cin >> x >> y >> w1 >> w2;
        d[x][x] = d[y][y] = 0;
        d[x][y] = d[y][x] = w1;
        a[x].push_back({ y, w1, w2 });
        a[y].push_back({ x, w1, w2 });
    }
    floyd();
    // cout << "st" << st << endl;
    dijkstra(st);
    int k;
    cin >> k;
    cout << st << endl;
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        cout << st;
        dfs(x);
        cout << endl;
        cout << dist[x] << " " << val[x] << endl;
    }
}
signed main()
{
    // IOS;
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

题解2

直接两遍floyd,这边需要学习floyd怎么存图

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define int long long
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2100;

int path[N][N], val[N][N], d[N][N];
int n, m, st;
void floyd()
{

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    val[i][j] = val[i][k] + val[k][j];
                    path[i][j] = k;
                } else if (d[i][j] == d[i][k] + d[k][j] && val[i][j] < val[i][k] + val[k][j]) {
                    val[i][j] = val[i][k] + val[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
    int sum = INF;
    for (int i = 1; i <= n; i++) {
        int res = 0;
        for (int j = 1; j <= n; j++) {
            res = max(res, d[i][j]);
        }
        if (res < sum) {
            sum = res;
            st = i;
        }
    }
}

void print(int i, int j)
{
    if (i == j)
        return;
    if (path[i][j] == 0)
        cout << "->" << j;
    else {
        print(i, path[i][j]);
        print(path[i][j], j);
    }
}

void solve()
{
    memset(d, 0x3f, sizeof d);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, w1, w2;
        cin >> x >> y >> w1 >> w2;
        d[x][x] = d[y][y] = 0;
        d[x][y] = d[y][x] = w1;
        val[x][x] = val[y][y] = 0;
        val[x][y] = val[y][x] = w2;
    }
    floyd();
    int k;
    cin >> k;
    cout << st << endl;
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        cout << st;
        print(st, x);
        cout << endl;
        cout << d[x][st] << " " << val[x][st] << endl;
    }
}
signed main()
{
    // IOS;
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}