2014-07-08发表2024-05-06更新算法设计

POJ 3255 Roadblocks （次短路问题）

解法有很多奇葩的地方，比如可以到达终点再跳回去再跳回来（比如有两个点）。。。。反正就是不能有最短路，不过没关系，算法都能给出正确结果

思想：和求最短路上的点套路一样，spfa先正着求一次，再反着求一次最短路，然后枚举每条边<i,j>找dist_zheng[i] + len<i,j> + dist_fan[j]的第二小值即可！注意不能用邻接矩阵，那样会MLE，应该用邻接表

/*
poj    3255
3808K	266MS
*/

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>

#define MAXN 200005
#define MAX_INT 2147483647

using namespace std;

int last[5005], dist_1[5005], dist_2[5005], n, m, gra[5005][5005];
bool mark[MAXN];

struct node
{
	int u;
	int v;
	int w;
	int next;
	node()
	{
		u = v = w = next = 0;
	}
}edge[MAXN];

void spfa( int dist[5005], int s )
{
	queue<int>myQueue;
	dist[s] = 0;
	memset(mark, false, sizeof(mark));
	mark[s] = true;
	myQueue.push(s);
	while( !myQueue.empty() )
	{
		int x = myQueue.front();
		myQueue.pop();
		mark[x] = false;
		int t = last[x];
		while( t )
		{
			if( dist[ edge[t].v ] > dist[x] + edge[t].w  )
			{
				dist[ edge[t].v ] = dist[x] + edge[t].w;
				if( !mark[ edge[t].v ] )
					myQueue.push( edge[t].v );
			}
			t = edge[t].next;
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1;i <= m;i ++)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		edge[i].u = edge[i + m].v = a;
		edge[i].v = edge[i + m].u = b;
		edge[i].w = edge[i + m].w = c;
		edge[i].next = last[a];
		last[a] = i;
		edge[i + m].next = last[b];
		last[b] = i + m;
	}
	memset( dist_1, 1, sizeof(dist_1) );
	spfa( dist_1, 1 );
	memset( dist_2, 1, sizeof(dist_2) );
	spfa( dist_2, n );
	int ans = MAX_INT, tmp = MAX_INT;
	for(int i = 1;i <= n;i ++)
	{
		int t = last[i];
		while( t )
		{
			if( dist_1[i] + dist_2[ edge[t].v ] + edge[t].w < tmp )
			{
				ans = tmp;
				tmp = dist_1[i] + dist_2[ edge[t].v ] + edge[t].w;
			}
			else if( dist_1[i] + dist_2[ edge[t].v ] + edge[t].w < ans 
					&& dist_1[i] + dist_2[ edge[t].v ] + edge[t].w != tmp )
				ans = dist_1[i] + dist_2[ edge[t].v ] + edge[t].w;
			t = edge[t].next;
		}
	}
	cout << ans << endl;
	return 0;
}

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

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;
}

2014-05-26发表2024-05-06更新算法设计

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 3255 Roadblocks （次短路问题）

POJ 1847 Tram（单源最短路径）

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

最新文章

分类

标签

归档

链接