首页 > 代码库 > SGU 145.Strange People

SGU 145.Strange People

2024-07-11 22:00:19   212人阅读

时间：0.25s
空间：4m

题意：

     其实就是求无环第K短路。

输入：

     给出n，m，k，分别代表，n个点，m条边，第k长路。     接下来m行，三个整数x，y，z，分别代表x，y之间有条费用为x的双向路。保证没有重边。

输出：

    第一行两个数a，b，第k小费用a，和经过的点的个数b。    接下来b个数，代表第k短的路径。


Sample Input

 

 5 10 3 1 2 6 1 3 13 1 4 18 1 5 35 2 3 14 2 4 34 2 5 17 3 4 22 3 5 15 4 5 34 1 5

Sample Output

 

 35 2  1 5



Solution：
         求k短路的算法，基本都是A*，这里的数据量比较小，可以采用二分答案。
         二分路径的长度，DFS求出有多少条路径的长度小于它，如果是（k-1）的话直接输出。
          
     
 PS:sgu在这一题上数据似乎出了问题，很多人都PE没法AC，我试着提交别人AC过的代码还是pe。
    因此代码没有AC，但对程序的正确性有把握。

参考代码：
#include <cstdio>const int INF = 111;int g[INF][INF], vis[INF], path[INF];int n, m, k, x, y, z, l, r, mid, leSum;int S, T, pd, len, tol;void dfs (int x, int dis) {	vis[x] = 1;	if (x == T) {		if (dis < mid)  leSum++;		if (!pd && dis == mid) leSum++, pd = 1;	}	else		for (int i = 1; i <= n; i++)			if (!vis[i] && g[x][i] && dis + g[x][i] <= mid)				dfs (i, dis + g[x][i]);	vis[x] = 0;}int check (int x) {	pd = leSum = 0;	dfs (S, 0);	return leSum;}int getPath (int x, int dis) {	vis[x] = 1;	if (x == T && dis == len) {		path[++tol] = x;		return pd = 1;	}	else		for (int i = 1; i <= n; i++) {			if (!vis[i] && g[x][i] && g[x][i] + dis <= len) {				if (getPath (i, dis + g[x][i]) ) path[++tol] = x;				if (pd) return 1;			}		}	vis[x] = 0;}int Search () {	while (l <= r) {		mid = l + (r - l >> 1);		int tem = check (mid);		if (tem == k)			return mid;		else if (tem > k)			r = mid - 1;		else l = mid + 1;	}	return -1;}int main() {	scanf ("%d %d %d", &n, &m, &k);	for (int i = 1; i <= m; i++) {		scanf ("%d %d %d", &x, &y, &z);		g[x][y] = g[y][x] = z, r += z;	}	scanf ("%d %d", &S, &T);	len = Search();	pd = tol = 0;	getPath (S, 0);	printf ("%d %d\n", len, tol);	for (int i = tol; i > 1; i--)		printf ("%d ", path[i]);		printf("%d\n",path[1]);	return 0;}

　　

　　






























        

            
                
                  
                
                

                    联系

                    我们