前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HDU 6386 Age of Moyu 2018 Multi-University Training Contest 7(最短路径dijkstra)

HDU 6386 Age of Moyu 2018 Multi-University Training Contest 7(最短路径dijkstra)

作者头像
用户2965768
发布2018-08-30 15:20:48
4400
发布2018-08-30 15:20:48
举报
文章被收录于专栏:wym

Age of Moyu

题意:第一行给出n,m,接下来有m条路,每一行给出 a b c ,从a到b 是c掌控。

  若下一条路与上一条路不属于一个c,需要缴费1. 输出从1到N的最小花费,不通则输出-1

题解:可以理解为换乘问题,换一辆车就多1花费,初始花费为1.

用最短路的思想,求出每个点的最小花费,用优先队列即可

代码语言:javascript
复制
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
#include <map>
using namespace std;
 
const int MAXN = 200005;
const int INF = 0x3f3f3f3f;
 
int N,M;
struct edge{
	int to,next,kind;
}E[MAXN*2];//双向边,双倍空间 

int head[100005],tot;
int dis[100005];
inline void Add(int from, int to ,int c)
{
	E[tot].to=to;
	E[tot].next=head[from];
	E[tot].kind=c;
	head[from]=tot++;
	E[tot].to=from;
	E[tot].next=head[to];
	E[tot].kind=c;
	head[to]=tot++; 
}
inline void init()
{
	tot=0;
	memset(head,-1,sizeof(head));
}
struct D{
	int num,w,kind;
	D(){}
	D(int _num,int _w,int _kind)
	{
		num=_num,w=_w,kind=_kind;
	}
};
struct cmp
{
	bool operator ()(D a,D b)
	{
		return a.w>b.w;
	}
};
int BFS(int x)
{
	priority_queue<D,vector<D>,cmp> q;
	
	fill(dis,dis+N+1,INF);
	
	dis[x]=0;
	q.push(D(x,0,-1));
	D t;
	while(!q.empty())
	{
		t=q.top(); q.pop();
		
		if(t.w>dis[t.num])continue;//若要这个点比到达这个点的最短花费多,跳过
		if(t.num==N)return t.w;
		
		for(int i=head[t.num];~i;i=E[i].next)//i=-1停止
		{
			int l;
			if(E[i].kind==t.kind)l=dis[t.num];
			else l=dis[t.num]+1;
			if(l<dis[E[i].to])
			{
				dis[E[i].to]=l;
				q.push(D(E[i].to,l,E[i].kind));//这个最短路需要更新,入队
			 } 
		}
	}
	return -1;
}
int main(){
    
    while(scanf("%d %d",&N,&M) == 2){
        init();
        if(M == 0){
            printf("-1\n");
            continue;
        }
        int a,b,c;
        for(int i=1 ; i<=M ; ++i){
            scanf("%d %d %d",&a,&b,&c);
            Add(a,b,c);
        }
        printf("%d\n",BFS(1));
    }
    
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018年08月14日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档