UVA 11374 Airport Express（优先队列优化dijstra + 枚举）

2020-12-09 08:58

阅读：732

标签：最短路

UVA Airport Express

题意：在Iokh市机场快线分为经济线和商业线。线路和速度价格都不同。你只有一张商业线车票，即最多只能坐一站商业线，其他时候只能坐经济线。找出一条去机场最快的线路。

思路：因为商业线只能坐一站，假如乘坐一条商业线(a,b)，那么起点到a,b到终点都必须是最短路。所以先预处理起点和终点到其他所有点的最短路，分别记为f()和g()，两次dijstra即可。那么我们只需枚举每条商业线求出所有的f(a)+T(a,b)+g(b)然后求最小即可。

1w是TLE，改成了优先队列优化的dijstra，白书上的模板。

2w是RE，题目中说边数最多1000条，开到1010仍然re,果断开到10010。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 510;
const int maxm = 10100;

struct node
{
	int u,v,w,next;
}edge[maxm];

int cnt,head[maxm];
int n,m,k;
int s,t;
int dis_s[maxm],dis_t[maxm];
int pre_s[maxm],pre_t[maxm];
int ans;
int path[maxm];

void init()
{
	cnt = 0;
	memset(head,-1,sizeof(head));

}

void add(int u, int v, int w)
{
	edge[cnt] = ((struct node){u,v,w,head[u]});
	head[u] = cnt++;
}

void dijstra(int u)
{
	int dis[maxn],pre[maxn];
	priority_queue ,vector >, greater > > que;
	bool vis[maxn];

	memset(vis,false,sizeof(vis));
	for(int i = 1; i  p = que.top();
		que.pop();
		int v = p.second;
		if(vis[v]) continue;
		vis[v] = true;

		for(int i = head[v]; i != -1; i = edge[i].next)
		{
			if( dis[edge[i].v] > dis[v] + edge[i].w)
			{
				dis[edge[i].v] = dis[v] + edge[i].w;
				pre[edge[i].v] = v;
				que.push(make_pair(dis[edge[i].v],edge[i].v));
			}
		}
	}

	if(u == s)
	{
		memcpy(dis_s,dis,sizeof(dis));
		memcpy(pre_s,pre,sizeof(pre));
	}
	if(u == t)
	{
		memcpy(dis_t,dis,sizeof(dis));
		memcpy(pre_t,pre,sizeof(pre));
	}
}


void solve()
{
	int mid_u,mid_v,u,v,w;
	int flag = 0;
	int cnt,tmp;
	scanf("%d",&k);
	for(int i = 0; i  0; i--)
			printf("%d ",path[i]);
		printf("%d\n",path[0]);

		printf("Ticket Not Used\n");
	}
	else
	{
		cnt = 0;
		tmp = mid_u;
		path[cnt++] = tmp;
		while(pre_s[tmp] != -1)
		{
			path[cnt++] = pre_s[tmp];
			tmp = pre_s[tmp];
		}
		for(int i = cnt-1; i >= 0; i--)
			printf("%d ",path[i]);

		cnt = 0;
		tmp = mid_v;
		path[cnt++] = tmp;
		while(pre_t[tmp] != -1)
		{
			path[cnt++] = pre_t[tmp];
			tmp = pre_t[tmp];
		}
		for(int i = 0; i 
UVA 11374 Airport Express（优先队列优化dijstra + 枚举）
标签：最短路
原文地址：http://blog.csdn.net/u013081425/article/details/24663855

上一篇：struts2+jquery验证注册用户是否存在

下一篇：php---下载功能

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：UVA 11374 Airport Express（优先队列优化dijstra + 枚举）
文章链接：http://soscw.com/index.php/essay/23520.html

亲，登录后才可以留言！

UVA 11374 Airport Express（优先队列优化dijstra + 枚举）

评论

热门文章

推荐文章

最新文章

置顶文章