思路整理
1.对于某一组的输入,我们从前向后两层循环遍历,将后面的点加入前面的点对应的邻接矩阵
2.堆优化dijkstra更新出最优解,此时dist[n]表示到达站点n的最少乘车次数,减去1即是最少换成次数
注意,这里不再考虑同一线路内的站的影响,而是将同意线路内的点看作前面的站可以直达后面任何一个站
AC代码(由于没有使用stringstream会稍微长一点,但是应该会快一点)
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1010
typedef pair<int,int> pii;
#define x first
#define y second
int e[MAXN],ne[MAXN],h[MAXN],idx;
int m,n;
int stop[MAXN];
int dist[MAXN];
bool st[MAXN];
//邻接表加边
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a],h[a]=idx++;
}
//堆优化dijkstra
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<pii,vector<pii>,greater<pii> > heap;
heap.push({0,1});
while(heap.size()){
auto u=heap.top();heap.pop();
int distance=u.x,ver=u.y;
if(st[ver]) continue;
st[ver]=true;
for(int i=h[ver];~i;i=ne[i]){
int j=e[i];
if(dist[j]>distance+1){
dist[j]=distance+1;
heap.push({dist[j],j});
}
}
}
return dist[n];
}
int main(){
memset(h,-1,sizeof(h));
scanf("%d%d",&m,&n);
//对于每一个线路记下来,再从前到后建立邻接表
for(int i=1;i<m;i++){
int tot,cnt=0;char ch;
scanf("%d%c",&tot,&ch);
stop[++cnt]=tot;
while(ch!='\n'){
scanf("%d%c",&tot,&ch);
stop[++cnt]=tot;
}
for(int i=1;i<=cnt;i++){
for(int j=i+1;j<=cnt;j++){
add(stop[i],stop[j]);
}
}
}
int cnt=0;
while(scanf("%d",&stop[++cnt])!=EOF);
for(int i=1;i<cnt;i++)
for(int j=i+1;j<cnt;j++)
add(stop[i],stop[j]);
//到这里为止以上都是输入部分,由于最后一行的输入没有'\n'因此要额外输入一遍
int res=dijkstra();
if(res>0x3f3f3f3f/2) puts("NO");
else printf("%d",res-1);
return 0;
}
此代码其他网站都通不过
什么网站?
洛谷和一本通都过不了
应该是主函数中输入问题
ok…
这个可以
大佬你好, 请问这里的M为什么要设为5e5+10啊? 设置为两倍的N就会segmentation fault…
因为边数很可能远大于两倍的N,只要每一条线路中的点数足够多(本蒟蒻的浅薄理解^^)
大佬orz