2014-05-28发表2024-04-30更新算法设计

POJ 1847 Tram（单源最短路径）

题意：轨道网，有若干转换器，每个转换器都和其他若干转换器相连，转换器初始指向第一个与其相连的转换器。问要到达终点需要最少转换多少次？

思路：可以用dijkstra单源最短路来做，把轨道网看做有向图（因为1第一个指向2，2的第一个不一定指向1），当前转换器处始指向的那个转换器之间的路径权值为0，其他路径权值为1，求一次起点到终点的最短路，结果就是最少转换次数，注意可能没有路径，这时要输出-1

代码：

/*
poj    1847
264K	0MS
*/
#include<cstdio>
#include<cstring>
#include<iostream>

#define MAXN 105
#define MAX_INT 2147483647

using namespace std;

int n,gra[MAXN][MAXN],dist[MAXN],sta,fin;

void init()
{
	memset(gra , -1 , sizeof(gra));
	cin>>n>>sta>>fin;
	for(int i = 1;i <= n;i ++)
	{
		int m,t;
		cin>>m>>t;
		gra[i][t] = 0;
		for(int j = 1;j < m;j ++)
		{
			scanf("%d",&t);
			gra[i][t] = 1;
		}
	}
	memset(dist , 1 , sizeof(dist));//这样可以整体赋一个较大的值 
	dist[sta] = 0;
}

int dijkstra()
{
	bool mark[MAXN] = {false};
	for(int i = 1;i <= n;i ++)
	{
		int Min = MAX_INT,tj;
		for(int j = 1;j <= n;j ++)
			if(dist[j] < Min && !mark[j])
			{
				Min = dist[j];
				tj = j;
			}
		mark[tj] = true;
		for(int j = 1;j <= n;j ++)
			if(!mark[j] && gra[tj][j] > -1)
				dist[j] = min(dist[j] , dist[tj] + gra[tj][j]);
	}
	if(dist[fin] == dist[0])
		return -1;
	return dist[fin];
}

int main()
{
	init();
	cout<<dijkstra()<<endl;
	return 0;
}

POJ 3268 Silver Cow Party（dijkstra单源最短路）

裸 dijkstra
思路：以x为源点，求到其他点的最短路，之后把邻接矩阵转置，再求一次x源

点的最短路，这样就一次是来的，一次是走的，相加迭代最大值即可

代码：

/*
poj    3268
8108K	47MS
*/
#include<cstdio>
#include<iostream>

#define MAXN 1005
#define MAX_INT 2147483647

using namespace std;

int gra_in[MAXN][MAXN],gra_out[MAXN][MAXN],n,m,p,dist_in[MAXN],dist_out[MAXN];

void init()
{
	cin>>n>>m>>p;
	for(int i = 1;i <= m;i ++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		gra_out[a][b] = c;
		gra_in[b][a] = c;
	}
}

void dijkstra(int gra[MAXN][MAXN] , int dist[MAXN])
{
	bool mark[MAXN] = {false};
	for(int i = 1;i <= n;i ++)
		dist[i] = MAX_INT;
	dist[p] = 0;
	for(int i = 1;i <= n;i ++)
	{
		int Min = MAX_INT,tj;
		for(int j = 1;j <= n;j ++)
		{
			if(mark[j])
				continue;
			if(Min > dist[j])
			{
				Min = dist[j];
				tj = j;
			}
		}
		mark[tj] = true;
		for(int j = 1;j <= n;j ++)
		{
			if(mark[j] || !gra[tj][j])
				continue;
			dist[j] = min(dist[j] , dist[tj] + gra[tj][j]);
		}
	}
}

int main()
{
	init();
	dijkstra(gra_in , dist_in);
	dijkstra(gra_out , dist_out);
	int Max = 0;
	for(int i = 1;i <= n;i ++)
		Max = max(Max , dist_in[i] + dist_out[i]);
	cout<<Max<<endl;
	return 0;
}

POJ 1847 Tram（单源最短路径）

POJ 3268 Silver Cow Party（dijkstra单源最短路）

最新文章

分类

标签

归档

链接