图

Posted on Edited on In

题面大意：有一个无向图：共 n 个节点，编号分别为 1~n，同时有 m 条无向边。不同于他研究的树，图中边和点都有各自的权值，第 i 条边的边权为 wi，第 i 个点的点权为 ci。从点 s 经过若干条边到点 t 的花费定义为：两点之间经过边的边权之和，加上经过的所有点（包括 s 和 t）的点权的最大值。现在 Makik 将给出 k 次询问，每次给出两个整数 s,t，询问从 s 到 t 的最小花费。（n属于250）

埋坑

大致意思就是看到数据范围很小，就联想Floyd

按权值从小到大转移，枚举转移点k（这种排序之后，把当前点作为最大权值的思想要学会借鉴）

\(dist(i,j)\)表示i与j之间的距离，\(ans(i,j)\)表示i与j之间的答案

因为暴力转移需要枚举一个最大值，所以我们考虑用排序来优化

我们美剧k,i,j实际上就是在枚举编号这么做的好处就是最大点权一定在i,j,k三点之间（想一想为什么）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int G = 256;

int n, m, K;
int dist[G][G], ans[G][G], c[G];

struct yhzhyhm
{
    int val, id;
    bool operator < (const yhzhyhm &x) const
    {
        return val < x.val;
    }
}yh[G];

inline void FLOYD()
{
//	sort(yh + 1, yh + 1 + n, cmp);
    sort(yh + 1, yh + 1 + n);
    int k, i, j;
    for (k = 1; k <= n; ++ k)
    {
        for (i = 1; i <= n; ++ i)
        {
            for (j = 1; j <= n; ++ j)
            {
                dist[i][j] = min(dist[i][j], dist[i][yh[k].id] + dist[yh[k].id][j]);
                ans[i][j] = min(ans[i][j], dist[i][j] + max(yh[k].val, max(c[i], c[j])));
            }
        }
    }
    return;
}

signed main()
{
    int i, x, y, z;
    n = read(), m = read(), K = read();
    memset(ans, 0x3f, sizeof ans), memset(dist, 0x3f, sizeof dist);
    for (i = 1; i <= n; ++ i)
    {
        yh[i].val = read();
        c[i] = yh[i].val, yh[i].id = i;
        ans[i][i] = yh[i].val, dist[i][i] = 0;
    }

    for (i = 1; i <= m; ++ i)
    {
        x = read(), y = read(), z = read();
        dist[x][y] = dist[y][x] = min(dist[x][y], z);
    }
    FLOYD();
    for (i = 1; i <= K; ++ i)
    {
        int s = read(), t = read();
        put(ans[s][t]);
    }
    return 0;
}