神奇的K短路(弗洛伊德)

众所周知，我们的q神666，这不，近来q神自己搭了个OJ玩，拉着我来测题。今天AC了q神的第一个题，写个博客记录一下。
打个广告daf_φ(❐_❐✧ 人丑就要多读书欢迎访问q神OJ

题目：
一天，HighLights实在是闲的不行，他选取了n个地点，n各地点之间共有m条路径，他想找到这m条路径组成的第k短路，你能帮助他嘛？

输入
第一行三个正整数，地点的数量n（2 <= n <= 2e5），边的数量m（1 <= m <= 2e5），k（1 <= k <= min(m, 200)）。

接下来m行，每行三个整数，边的一个顶点u（1<=u<=n），边的另一个顶点v(1<=v<=n)，边的权值w(1<=w<=1e5)，代表u有一条到v权值为w的单向边。

输出
输出k短路的权值。

样例
输入：　　　　　　　　　　　　　　　　　　　输出：
　　　4 4 3　　　　　　　　　　　　　　　　　　　16
　　　1 3 27
　　　1 4 16
　　　1 2 15
　　　2 4 3

刚开始看到这题，乍一想，这不就是弗洛伊德板子题吗，然后很光荣的RE了。回头一看数据范围，2e5的边，弗洛伊德肯定炸了，再一看k最大只有200，所以有了以下想法：

1、对所有边进行一个排序；
2、从小到大选出前K条边；
3、对选出的边的点进行重新编号；
4、这下最大只有200^3的复杂度了；
5、跑一遍弗洛伊德，然后求出第k小就可以了

悄咪咪的说一句，q神说这就是个简单的思维题，5555555555555555555

愉快AC

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
#define inf 1e9 + 5
const int maxn = 2e5 + 10;
int n, m, k;
struct edge {
	int from, to;
	int cost;
}es[maxn];
map<int, int>mp;
int d[500][500];
bool cmp(edge a, edge b) {
	return a.cost < b.cost;
}
void init() {
	//调用弗洛伊德之前的处理，d[i][i]=0,其余是inf;注意inf的大小，大了会溢出，小了会被当做边
	for (int i = 1; i <= k * 2; i++) {
		for (int j = 1; j <= k * 2; j++) {
			if (i == j)
				d[i][j] = 0;
			else
				d[i][j] = inf;
		}
	}
}
void floyd(int k) {
	for (int t = 1; t <= k; t++) {
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j <= k; j++) {
				if (d[i][t] != inf && d[t][j] != inf && d[i][t] != 0 && d[t][j] != 0)
					d[i][j] = min(d[i][j], d[i][t] + d[t][j]);
			}
		}
	}
}
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < m; i++)
		scanf("%d%d%d", &es[i].from, &es[i].to, &es[i].cost);
	sort(es, es + m, cmp);
	init();
	int t = 1;
	for (int i = 0; i < k; i++) {
		int x = es[i].from;
		int y = es[i].to;
		if (!mp[x])
			mp[x] = t++;
		if (!mp[y])
			mp[y] = t++;
		d[mp[x]][mp[y]] = es[i].cost;
		//d[mp[y]][mp[x]] = es[i].cost;
	}
	floyd(t - 1);
	priority_queue<int, vector<int>, less<int> >pq;
	/*
	for (int i = 1; i <= t; i++) {
		for (int j = 1; j <= t; j++) {
			cout << d[i][j] << " ";
		}
		cout << endl;
	}
	*/
	for(int i = 1; i <= t - 1; i++){
		for(int j = 1; j <= t - 1; j++){
			if(pq.size() < k && d[i][j] != 0 && d[i][j] != inf)
				pq.push(d[i][j]);
			else if(pq.size() >= k){
				if(pq.top() > d[i][j] && d[i][j] != 0){
					pq.pop();
					pq.push(d[i][j]);
				}
			}
		}
	}

	printf("%d\n", pq.top());

	return 0;
}

神奇的K短路(弗洛伊德思维题)

神奇的K短路(弗洛伊德)

推荐阅读