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("-1n");
continue;
}
int a,b,c;
for(int i=1 ; i<=M ; i){
scanf("%d %d %d",&a,&b,&c);
Add(a,b,c);
}
printf("%dn",BFS(1));
}
return 0;
}
