图论——单源点最短路径建图方式

单源点，正权图，求到终点的最短路径。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 2510, M = 6210 * 2;
int dist[N];
bool vis[N];
int h[N], ne[M], w[M], e[M], tot;
int n, m, st, ed;
int q[N];
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[st] = 0;
    q[0] = st;
    vis[st] = 1;
    int hh = 0, tt = 1;
    while (hh != tt)
    {
        int t = q[hh ++];
        vis[t] = 0;
        if (hh == N) hh = 0;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!vis[j])
                {
                    q[tt ++] = j;
                    vis[j] = 1;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return dist[ed];
}
int main()
{
    cin >> n >> m >> st >> ed;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    int t = spfa();
    cout << t;
    return 0;
}

走一遍最短路算法，如果从第1个点到第$i$个点的最短距离$dist[i]$不存在，即无法到达第$i$个点，则说明不是所有哨所都能收到信。如果所有哨所都能到达，则在$dist[i]$中找最大值点。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int ,int> PII;
const int N = 110, M = 210 * 2;
int h[N], w[M], e[M], ne[M];
int tot;
int dist[N];
bool st[N];
int n, m;
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0,1});
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = 1;
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    int maxn = 0;
    for (int i = 2; i <= n; i ++ )
    {
        if (dist[i] == 0x3f3f3f3f) return -1;
        maxn = max(maxn, dist[i]);
    }
    return maxn;
}
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    int t = dijkstra();
    cout << t;
    return 0;
}

在本题中，我们需要考虑以每个点作为特定的牧场，去求所有奶牛到该点的距离之和，如果我们使用Floyd算法的话，时间复杂度为$O(n^3)$，会超时，因此本题可以采用堆优化版的dijkstra算法做$n$遍，时间复杂度为$nmlog(n)$，也可以做$n$遍spfa,时间复杂度大概为$O(nm)$。

#include <iostream>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 810, M = 1460 * 2;
int id[N];
int h[N], ne[M], e[M], w[M];
int tot;
int n, p, m;
int q[N];
bool st[N];
int dist[N];
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
int spfa(int start)
{
    memset(dist, 0x3f, sizeof dist);
    dist[start] = 0;
    int hh = 0, tt = 1;
    q[0] = start;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        st[t] = 0;
        if (hh == N) hh = 0;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = 1;
                }
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (dist[id[i]] == INF) return INF;
        res +=  dist[id[i]];
    }
    return res;
}
int main()
{
    cin >> n >> p >> m;
    for (int i = 1; i <= n; i ++ )
        cin >> id[i];
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    int res = INF;
    for (int i = 1; i <= p; i ++ )
        res = min(res, spfa(i));
    cout << res;
    return 0;
} 

某一条路径上需要扣除的手续费是$z\%$，则意味着能够保留的比例是$1-z\%$。我们的目标是想要找到从$A$到$B$的一条乘积最大的道路。假设有一条转账路径，路径长度(能够保留的比例)分别为$a,b,c,d$,乘积最大，也就是等价于让$log(abcd)=loga+logb+logc+logd$最大。因为$w\in (0,1]$，所以边权$logw$一定是非正数，也正因此，本题可以采用dijkstra求最大值来做。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 2010;
double g[N][N];
double dist[N];
bool st[N];
int n, m, S, T;
double dijkstra()
{
    dist[S] = 1;
    for (int i = 1; i <= n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] < dist[j]))
                t = j;
        st[t] = 1;

        for (int j = 1; j <= n; j ++ )
        {
            dist[j] = max(dist[j], dist[t] * g[t][j]);
        }
    }
    return dist[T];
}

int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        double d = (100.0 - c) / 100;
        g[a][b] = g[b][a] = max(g[a][b], d);
    }
    cin >> S >> T;
    double t = dijkstra();
    printf("%.8lf", 100 / t);
    return 0;
}

对于每一条路线来说，例如$2-1-3-5$，我们可以认为存在$(2,1),(2,3),(2,5),(1,3),(1,5),(3,5)$这些长度为1的连接，即每个点到其后的点都存在长度为1的连接，这样一来就可以表示在同一条路线中，我们某个点只需要乘一次车就能到达后面的点。我们可以使用单源点最短路算法求出最少乘车次数，最少乘车次数减去1就是题目要求求的最少换乘次数。因为本题只存在长度为1的边，我们可以使用BFS来做。

#include <iostream>
#include <cstring>
#include <sstream>
using namespace std;
const int N = 510, M = 500010;
int stop[N];
int dist[N];
string line;
bool g[N][N];
int q[N];
int n, m;
int bfs()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int hh = 0, tt = 0;
    q[hh] = 1;
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 1; i <= n; i ++ )
        {
            if (g[t][i] && dist[i] > dist[t] + 1)
            {
                dist[i] = dist[t] + 1;
                q[++ tt] = i;
            }
        }
    }
    return dist[n];
}
int main()
{
    cin >> m >> n;
    getline(cin, line);
    while (m -- )
    {
        getline(cin, line);
        stringstream ssin(line);
        int p, cnt = 0;
        while (ssin >> p) stop[++ cnt] = p;
        for (int i = 1; i <= cnt; i ++ )
            for (int j = i + 1; j <= cnt; j ++ )
                g[stop[i]][stop[j]] = 1;
    }
    int ans = bfs();
    if (ans == 0x3f3f3f3f) puts("NO");
    else cout << max(0, ans - 1) << endl;
    return 0;
}

我们可以把每一个物品看作是一个节点，每个物品的替代品到该物品都存在单向连接，边权就是优惠价格。我们可以把探险家看作是一个0号节点，存在和所有物品直接相连的边，边权就是这个物品的价格，这样一来我们就完成了建图。因为本题对等级限制有要求，因此我们可以在$[level[1]-m,level]-[level[1],level+m]$范围内枚举等级的上下界，以保证既符合等级限制要求又能保证可以到达酋长节点。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110, M = N * N;
int h[N], e[M], ne[M], w[M];
int n, m;
int tot;
int dist[N];
bool st[N];
int q[N];
int level[N];
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
int dijkstra(int down, int up)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[0] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 0});
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = 1;
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (level[j] >= down && level[j] <= up && dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    return dist[1];
}
int main()
{
    cin >> m >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int p, x;
        cin >> p >> level[i] >> x;
        add(0, i, p);
        while (x -- )
        {
            int t, v;
            cin >> t >> v;
            add(t, i, v);
        }
    }
    int res = 0x3f3f3f3f;
    for (int i = level[1] - m; i <= level[1]; i ++ )
        res = min(res, dijkstra(i, i + m));
    cout << res;
    return 0;
}