题目大意是说给定一个无向图,要求出所有的点对之间的最短路之中第k小的值。思路很简单,就是用Floyd算法跑一遍然后排序就行,但是点的数目给的比较多,用邻接矩阵存储会爆内存。注意到第k小的最短路权值至多为第k短的边权,因此选择前k条边连接的至多2k个点,仅仅考虑它们之间的路径来跑最短路,就OK了。
AC代码
#include <iostream> #include <algorithm> #include <vector> #include <map> #ifdef _MSC_VER #define scanf scanf_s #endif // _MSC_VER #ifndef ONLINE_JUDGE #define debug(x) std::cout<<x<<std::endl; #else #define debug(x) ; #endif using namespace std; const long long INF = static_cast<long long>(1e15 + 7); const int MAXN = 2e5 + 5; const int MAXM = 2e5 + 5; struct EDGE { int from, to, weight; EDGE(int f, int t, int w):from(f),to(t),weight(w){} }; int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); vector<EDGE> edge; for (int i = 0; i < m; ++i) { static int f, t, w; scanf("%d%d%d", &f, &t, &w); edge.push_back(EDGE(f, t, w)); } sort(edge.begin(), edge.end(), [](const EDGE& a, const EDGE& b) {return a.weight < b.weight; }); int up = min(k, m); vector<vector<long long>> dis(2*k, vector<long long>(2*k, INF)); vector<int> points; for (int i = 0; i < up; ++i) { points.push_back(edge[i].from); points.push_back(edge[i].to); } sort(points.begin(), points.end()); auto ed = unique(points.begin(), points.end()); map<int, int> bij; for (auto it = points.begin(); it != ed; ++it) { bij[*it] = it - points.begin(); } for (int i = 0; i < up; ++i) { dis[bij[edge[i].from]][bij[edge[i].to]] = edge[i].weight; dis[bij[edge[i].to]][bij[edge[i].from]] = edge[i].weight; } for (int s = 0; s < 2 * k; ++s) { for (int i = 0; i < 2 * k; ++i) { for (int j = 0; j < 2 * k; ++j) { if (dis[i][s] + dis[s][j] < dis[i][j]) dis[i][j] = dis[i][s] + dis[s][j]; } } } vector<long long> tmp; for (int i = 0; i < 2 * k; ++i) { for(int j=i+1;j<2*k;++j){ tmp.push_back(dis[i][j]); } } sort(tmp.begin(), tmp.end()); printf("%lld\n", tmp[k - 1]); return 0; }
Comments | NOTHING