题目描述
多个起点,一个终点的有向图的最短路径问题
输入样例
5 8 5
1 2 2
1 5 3
1 3 4
2 4 7
2 5 6
2 3 5
3 5 1
4 5 1
2
2 3
4 3 4
1 2 3
1 3 4
2 3 2
1
1
输出样例
1
-1
算法
(Dijkstra) O(T∗mlog(n))
考虑将输入的边反向构建,于是原问题就变成一个起点,多个终点的最短路问题,跑一遍最短路算法然后枚举终点即可。
时间复杂度
多组测试数据,每组测试数据用堆优化Dijkstra,因此时间复杂度是O(T∗mlog(n))
C++ 代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1010, M = 20010, INF = 0x3f3f3f3f;
int n, m, s, k;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra() {
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, s});
while (q.size()) {
auto t = q.top(); q.pop();
int v = t.y;
if (st[v]) continue;
st[v] = true;
for (int i = h[v]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[v] + w[i]) {
dist[j] = dist[v] + w[i];
q.push({dist[j], j});
}
}
}
}
int main() {
while (cin >> n >> m >> s) {
memset(h, -1, sizeof h);
idx = 0;
while (m -- ) {
int a, b, c; cin >> a >> b >> c;
add(b, a, c);
}
dijkstra();
cin >> k;
int ret = INF;
for (int i = 0; i < k; i ++ ) {
int x; cin >> x;
ret = min(ret, dist[x]);
}
if (ret == INF) puts("-1");
else cout << ret << endl;
}
return 0;
}
狂赞
而且这个反向建边真的很妙
dalao们好像都在用spfa
终于见到用dijkstra的啦!!