图的存储

对于有向图而言，有两种方式的图存储方式

• 邻接表

  对于邻接表而言，推荐采用链式前向星数组的形式， 增加节点和便利节点的方式如下

  // e[i] : 代表另外一个端点
  // nxt[i] : 同一个链表下的下一个索引
  // w[i] : 边长
  // h[i] : 指向端点i的头节点
  // idx : 下一条边的索引
  int e[M], nxt[M], w[M], h[N], idx;
  
  // 一些初始化
  void init() {
      // 刚开始所有的点都指向 -1
      memset(h, -1, sizeof h);
  }
  
  // 添加a指向b且长度为c的有向边
  void add(int a, int b, int c) {
      e[idx] = b, w[idx] = c, nxt[idx] = h[a], h[a] = idx++;
  }
  
  // 遍历
  void demo {
      int cur = 1;
      for(int i=h[cur];i!=-1;i=nxt[i]) {
          // 另外一边
          int k = e[i];
          // ....
      }
  }
  
  

• 邻接矩阵

  对于二维数组 g[i][j] 表示点 i 指向 j 存在 g[i][j] 长度的有向边

最短路算法

1. Dijkstra

这个算法采用了贪心策略，在每次可以遍历可以确定一个最优点

• 朴素的Dij 复杂度是 O($n^2$)，n 是点数
• 朴素算法的瓶颈在于找出全局最小点，堆优化Dij采用最小堆priority_queue<int, vector<int>, greater<int>>来对 dist[i] 维护，时间复杂度是 O($mlogn$) ，其中m是边的个数

代码模板（朴素）

const int N = 2021;

int d[N][N], dist[N];
bool st[N];

// 使用的是邻接矩阵
void dijkstra() {
    dist[S] = 0;
    for (int i = 1; i <= n; i++) {
        int cur = -1;
        // 找最小的那个（前提是这个边没有被找过）
        for (int j = 1; j <= n; j++) if (!st[j] && (cur == -1 || dist[cur] > dist[j])) cur = j;
        st[cur] = true;
        // 更新最小点周围的边长
        for (int j = 1; j <= n; j++) if (dist[cur] + d[cur][j] < dist[j]) dist[j] = dist[cur] + d[cur][j];
    }
}

代码模板（堆优化）

typedef pair<int, int> PII;

int dist[N], st[M];

// 使用的是邻接表
void 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] = true;

        for (int i = h[ver]; i != -1; 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});
            }
        }
    }
}

2. SPFA（Shortest Path Fast Algorithm）

这个算法是广搜的变形，很明显，当路径长度为1的时候，我们可以用BFS来算最短路。

这个算法在随机图上的时间复杂度是O($km$), k是一个很小的常数，对于特殊图，可能会达到O($mn$) 的时间复杂度。

这个算法是可以处理负权边的

代码模板

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

using namespace std;

int n, m;

const int N = 1e5 + 10, M = 1e5 + 10;

int e[M], w[M], h[N], ne[M], idx;

int dist[N], q[N], hh, tt;
bool st[N];

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

int main() {
    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);
    
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }


    // spfa
    st[1] = true;
    q[tt++] = 1;
    dist[1] = 0;
    
    while(hh != tt) {
        int u = q[hh++];
        st[u] = false;
        if(hh == N) hh = 0;
        for(int i=h[u];~i;i=ne[i]) {
            int j = e[i];
            if(dist[j] > dist[u] + w[i]) {
                dist[j] = dist[u] + w[i];
                if(!st[j]) {
                    st[j] = true;
                    q[tt++] = j;
                    if(tt == N) tt = 0;
                }
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", dist[n]);
    return 0;
}

3. Floyd（多源）

这个算法可以通过O($n^3$)的时间复杂度算出任意两个点的最短路，是一种dp思路。

代码模板

int dist[N][N];

void floyd() {
    for(int k=1;k<=n;k++) 
        for(int i=1;i<=n;i++) 
            for(int j=1;j<=n;j++) 
    			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

例题讲解

AcWing 1129. 热浪

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

using namespace std;

const int N = 2510, M = 6210 << 1;

int start, en, n, m;

int e[M], nxt[M], w[M], h[N], idx;

int dist[N], st[N];

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

void spfa(int u) {
    queue<int> que;
    que.push(u);
    dist[u] = 0, st[u] = 1;
    while (!que.empty()) {
        int cur = que.front();
        que.pop();
        st[cur] = 0;
        for (int i = h[cur]; i != -1; i = nxt[i]) {
            int k = e[i];
            if (dist[cur] + w[i] < dist[k]) {
                dist[k] = dist[cur] + w[i];
                if (st[k] == 0) que.push(k);
            }
        }
    }
}

int main() {
    cin >> n >> m >> start >> en;
    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    spfa(start);
    cout << dist[en] << endl;
    return 0;
}

AcWing 1128. 信使

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

using namespace std;

int n, m;

const int N = 110, INF = 0x3f3f3f3f;

int dist[N][N];

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

    memset(dist, 0x3f, sizeof dist);

    for (int i = 1; i <= n; i++) dist[i][i] = 0;

    for (int i = 1; i <= m; i++) {
        int p1, p2, dis;
        cin >> p1 >> p2 >> dis;
        dist[p1][p2] = dist[p2][p1] = min(dist[p1][p2], dis);
    }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        if (dist[1][i] == INF) {
            ans = -1;
            break;
        }
        ans = max(ans, dist[1][i]);
    }
    cout << ans << endl;
    return 0;
}

AcWing 1127. 香甜的黄油

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

using namespace std;

int n, p, c;

const int N = 810, M = 510, T = 1510 * 2, INF = 0x3f3f3f3f;

int r[N], dist[T];
bool st[T];

int ne[T], w[T], e[T], h[N], idx;

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

void spfa(int S) {
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    queue<int> que;
    que.push(S);
    dist[S] = 0;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        st[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[u] + w[i] < dist[j]) {
                dist[j] = dist[u] + w[i];
                if (!st[j]) que.push(j), st[j] = true;
            }
        }
    }
}


int main() {
    cin >> n >> p >> c;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) cin >> r[i];
    for (int i = 1; i <= c; i++) {
        int a, b, wi;
        cin >> a >> b >> wi;
        add(a, b, wi), add(b, a, wi);
    }
    int ans = INF;
    for (int i = 1; i <= p; i++) {
        spfa(i);
        int sum = 0, j = 1;
        for (; j <= n; j++) {
            if (dist[r[j]] == INF) break;
            sum += dist[r[j]];
        }
        if (j <= n) continue;
        ans = min(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

AcWing 1126. 最小花费

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

using namespace std;

int n, m, S, T;

const int N = 2010, INF = 0x3f3f3f3f;

double d[N][N], dist[N];
bool st[N];

double dijkstra() {
    dist[S] = 1.0;
    for (int i = 1; i <= n; i++) {
        int cur = -1;
        for (int j = 1; j <= n; j++) if (!st[j] && (cur == -1 || dist[cur] < dist[j])) cur = j;
        st[cur] = true;
        for (int j = 1; j <= n; j++) if (dist[cur] * d[cur][j] > dist[j]) dist[j] = dist[cur] * d[cur][j];
    }
    return dist[T];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < N; i++) d[i][i] = 1;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        d[x][y] = d[y][x] = (100.0 - z * 1.0) / 100.0;
    }
    cin >> S >> T;
    printf("%.8lf\n", 100.0 / dijkstra());
    return 0;
}

AcWing 920. 最优乘车

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

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int g[N][N], dist[N], stop[N];
bool st[N];
int n, m;

void spfa() {
    memset(dist, 0x3f, sizeof dist);
    queue<int> que;
    dist[1] = 0;
    que.push(1);
    st[1] = true;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        st[u] = false;
        for (int i = 1; i <= n; i++) {
            if (g[u][i] + dist[u] < dist[i]) {
                dist[i] = g[u][i] + dist[u];
                if (!st[i]) que.push(i);
            }
        }
    }
}

int main() {
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < N; i++) g[i][i] = 0;
    cin >> m >> n;
    string line;
    getline(cin, line);
    while (m--) {
        getline(cin, line);
        stringstream ssin(line);
        int cnt = 0, p;
        while (ssin >> p) stop[cnt++] = p;
        for (int i = 0; i < cnt; i++) for (int j = i + 1; j < cnt; j++) g[stop[i]][stop[j]] = 1;
    }
    spfa();
    if (dist[n] == INF) puts("NO");
    else cout << max(0, dist[n] - 1) << endl;
    return 0;
}

AcWing 903. 昂贵的聘礼

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

using namespace std;

int n, m;
int P, L, X;
int T, V;

const int N = 110, M = 110 * 110;

struct Item {
    int id, p, l;
};

unordered_map<int, Item> i2i;

unordered_map<int, unordered_map<int, int>> mp;

int ne[M], w[M], h[N], e[M], idx;

int dist[N], st[M];

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

typedef pair<int, int> PII;


void dijkstra()  // 求1号点到n号点的最短路距离
{
    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] = true;

        for (int i = h[ver]; i != -1; 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});
            }
        }
    }
}


void dijkstra(int l, int r) {
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[n + 1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, n + 1});

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (i2i[j].l < l || i2i[j].l > r) continue;
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}


int main() {
    memset(h, -1, sizeof h);

    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &P, &L, &X);
        Item item = {i, P, L};
        for (int j = 1; j <= X; j++) {
            scanf("%d%d", &T, &V);
            mp[T][i] = V;
        }
        i2i[i] = item;
    }

    // 建边
    for (auto[k, v] : mp) {
        for (auto[k1, v1] : v) {
            if (abs(i2i[k1].l - i2i[k].l) <= m) {
                add(k, k1, v1);
            }
        }
    }

    // 虚拟节点
    for (int i = 1; i <= n; i++) add(n + 1, i, i2i[i].p);

    int ans = 0x3f3f3f3f;
    int le = i2i[1].l;
    for (int i = le - m; i <= le; i++) {
        dijkstra(i, i + m);
        ans = min(ans, dist[1]);
    }
    cout << ans << endl;
    return 0;
}

AcWing 1135. 新年好

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

using namespace std;

const int N = 50010, M = 2e5 + 10, INF = 0x3f3f3f3f;

int n, m, a, b, c, d, f;

int ne[M], w[M], h[N], e[M], idx;

int dist[6][N];

bool st[N];

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

// void spfa(int distIdx, int S) {
//     auto &dis = dist[distIdx];
//     memset(st, 0, sizeof st);
//     memset(dis, 0x3f, sizeof dis);
//     queue<int> que;
//     que.push(S);
//     dis[S] = 0;
//     while(!que.empty()) {
//         int t = que.front();
//         que.pop();
//         st[t] = false;
//         for(int i=h[t];~i;i=ne[i]) {
//             int j = e[i];
//             if(dis[t] + w[i] < dis[j]) {
//                 dis[j] = dis[t] + w[i];
//                 if(!st[j]) que.push(j), st[j] = true;
//             }
//         }
//     }
// }

typedef pair<int, int> PII;

void dijkstra(int distIdx, int S)  // 求1号点到n号点的最短路距离
{
    auto &dis = dist[distIdx];
    memset(dis, 0x3f, sizeof dis);
    memset(st, 0, sizeof st);
    dis[S] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, S});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dis[j] > dis[ver] + w[i])
            {
                dis[j] = dis[ver] + w[i];
                heap.push({dis[j], j});
            }
        }
    }
}

int main() {
    cin >> n >> m;
    cin >> a >> b >> c >> d >> f;
    memset(h, -1, sizeof h);
    for(int i=1;i<=m;i++) {
        int a1, b1, c1;
        scanf("%d%d%d", &a1, &b1, &c1);
        add(a1, b1, c1), add(b1, a1, c1);
    }
    dijkstra(0, 1);
    dijkstra(1, a);
    dijkstra(2, b);
    dijkstra(3, c);
    dijkstra(4, d);
    dijkstra(5, f);
    vector<int> nums = {a, b, c, d, f};
    sort(nums.begin(), nums.end());
    unordered_map<int, int> mp;
    mp[a] = 1, mp[b] = 2, mp[c] = 3, mp[d] = 4, mp[f] = 5; 

    int ans = INF;
    do {
        int t = dist[0][nums[0]];
        for(int i=0;i<4;i++) {
            t += dist[mp[nums[i]]][nums[i+1]];
        }
        ans = min(ans, t);
    } while(next_permutation(nums.begin(), nums.end()));
    cout << ans << endl;
    return 0;
}