acwing算法提高之图论--单源最短路的扩展应用

1 介绍

本专题用来记录使用。。。。

2 训练

题目1：1137选择最佳线路

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 1010, M = 20010;
int n, m;
int dist[N];
int st[N];
vector<vector<pair<int,int>>> g;
vector<int> snodes;
int enode; 
int w;void spfa() {//cout << " ====== " << endl;memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);queue<int> q;for (auto snode : snodes) {//cout << "snode = " << snode << endl;dist[snode] = 0;q.push(snode);st[snode] = true; //已经在队列中了}while (!q.empty()) {auto t = q.front();q.pop();st[t] = false;for (auto [b, w] : g[t]) {if (dist[b] > dist[t] + w) {dist[b] = dist[t] + w;if (!st[b]) {q.push(b);st[b] = true;}}}}return;
}int main() {while (cin >> n >> m >> enode) {g.clear();g.resize(n + 10);for (int i = 0; i < m; ++i) {int a, b, c;cin >> a >> b >> c;g[a].emplace_back(b, c);}cin >> w;snodes.resize(w);for (int i = 0; i < w; ++i) cin >> snodes[i];spfa();if (dist[enode] == 0x3f3f3f3f) cout << "-1" << endl;else cout << dist[enode] << endl;}return 0;
}

题目2：