专栏首页Zaqdt_ACMHDU 3499 Flight(分层图最短路)

HDU 3499 Flight(分层图最短路)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3499

       题意是有n个城市,m条路线,然后有一张半价票,问从起点到终点的最小花费。

       这道题如果不知道分层图的话很容易会想到一种错误的解法,就是跑一遍最短路,然后将最大的权值/2,可以自己试着造几个样例试试这样是不对的(比如最短路相同,但是路径不同的情况),所以这道题用分层图去跑,因为只有一张半价票,所以只需要建两层图就好了。因为如果可以到达终点的话,这张半价票肯定是要用的,所以最终的结果就一定是ma[s]到ma[t] + n,至于建图的过程看代码自己理解吧。(用的是链式前向星存图方式,所以对于边数应该是题目要求的3倍)


AC代码:

#include <bits/stdc++.h>
#define maxn 100005 << 1
#define maxm 500005 << 2
#define ll long long
const ll inf = 0x3f3f3f3f3f3f3f3f;
using namespace std;
struct Node{
	int to, next, w;
	bool operator < (const Node &a) const{
		return a.w < w;
	}
}Edge[maxm], Now, Next;
int head[maxn],num;
ll dist[maxn];
bool vis[maxn];
int n,m;

void init(){
	for(int i=0;i<=n*2;i++) head[i] = -1;
	num = 0;
}

void add(int u,int v,int w){
	Edge[num].to = v;
	Edge[num].w = w;
	Edge[num].next = head[u];
	head[u] = num ++;
}

void dijkstra(int s){
	for(int i=0;i<=2*n;i++){
		dist[i] = inf;
		vis[i] = false;
	}
	dist[s] = 0;
	priority_queue<Node> q;
	Now.to = s;
	q.push(Now);
	while(!q.empty()){
		int u = q.top().to;
		q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(int i=head[u];i!=-1;i=Edge[i].next){
			int v = Edge[i].to;
			if(!vis[v] && dist[v] > dist[u] + Edge[i].w){
				dist[v] = dist[u] + Edge[i].w;
				Next.to = v;
				Next.w = dist[v];
				q.push(Next);
			}
		}
	}
}

int main()
{
	while(~scanf("%d%d",&n,&m)){
		init();
		map<string,int> ma;
		int pos = 1;
		int w;
		char u[15],v[15],s[15],t[15];
		for(int i=0;i<m;i++){
			scanf("%s%s%d",u,v,&w);
			if(!ma[u]) ma[u] = pos ++;
			if(!ma[v]) ma[v] = pos ++;
			add(ma[u], ma[v], w);
			add(ma[u] + n, ma[v] + n, w);
			add(ma[u], ma[v] + n, w / 2);
		}
		scanf("%s%s",s,t);
		if( !ma[s] || !ma[t]){
			puts("-1");
			continue;
		}
		dijkstra(ma[s]);
		printf("%lld\n", dist[ma[t] + n] == inf ? -1 : dist[ma[t] + n]);
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 牛客寒假算法基础集训营4 F. Applese的QQ群(二分+拓扑排序+dfs)

    题目链接:https://ac.nowcoder.com/acm/contest/330/F

    Ch_Zaqdt
  • POJ Test for Job(DAG上拓扑排序)

           题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。

    Ch_Zaqdt
  • NYOJ 139 我排第几个(康拓展开+康拓展开逆运算)

           康拓展开的裸题,对于康拓展开的定义是求当前的排列位于全排列中的第几个,比如132就是123的全排列的第二个,对于康拓展开的求法就是ans = ai...

    Ch_Zaqdt
  • C语言生成固定范围的随机数

    本文为仙士可原创文章,转载无需和我联系,但请注明来自仙士可博客www.php20.cn

    仙士可
  • 动画+原理+代码+优化,解读十大经典排序算法

    排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

    用户1655470
  • 动画+原理+代码+优化,解读十大经典排序算法

    排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

    好好学java
  • 动画+原理+代码+优化,解读十大经典排序算法

    排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

    搜云库技术团队
  • SmallSum-归并排序-小和问题(逆序对)

    例如:数组[4,2,5,1,7,3,6] 第一个元素4比2大,不算小和,5比4和2都大,那就是4+2=6;1比4和2和5都小,不算小和;7比前面的都大,那就是上...

    sr
  • iOS-关于随机数总结rand()random()drand48()arc4random()rac4random_uniform(int upper_bound)实例应用

    用户2215591
  • ECJTUACM16 Winter vacation training #5 题解&源码

    A-------------------------------------------------------------------------------...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券