程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 11374 Airport Express（優先隊列優化dijstra + 枚舉）

UVA 11374 Airport Express（優先隊列優化dijstra + 枚舉）

編輯：C++入門知識

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 <= n; i++)
	{
		dis[i] = (i == u ? 0 : INF);
	}

	que.push(make_pair(dis[u],u));
	pre[u] = -1;

	while(!que.empty())
	{
		pair 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 < k; i++)
	{
		scanf("%d %d %d",&u,&v,&w);

		if(dis_s[u] + dis_t[v] + w < ans)
		{
			ans = dis_s[u] + dis_t[v] + w;
			mid_u = u;
			mid_v = v;
			flag = 1;
		}
		if(dis_s[v] + dis_t[u] + w < ans)
		{
			ans = dis_s[v] + dis_t[u] + w;
			mid_u = v;
			mid_v = u;
			flag = 1;
		}
	}

	if(flag == 0)
	{
		cnt = 0;
		tmp = t;
		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]);
		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 < cnt-1; i++)
			printf("%d ",path[i]);
		printf("%d\n",path[cnt-1]);

		printf("%d\n",mid_u);
	}
	printf("%d\n",ans);
}

int main()
{
	int item = 0;
	while(~scanf("%d %d %d",&n,&s,&t))
	{
		if(item)
			printf("\n");
		init();
		int u,v,w;
		scanf("%d",&m);
		for(int i = 0; i < m; i++)
		{
			scanf("%d %d %d",&u,&v,&w);
			add(u,v,w);
			add(v,u,w);
		}

		dijstra(s);	//預處理
		dijstra(t);

		ans = dis_s[t];

		solve();
		item++;
	}
	return 0;
}